DEV Community

ZeeshanAli-0704
ZeeshanAli-0704

Posted on

Inorder Traversal

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 *

  /**
   * The goal is to maintain a stack of nodes to visit as we traverse
   * down the tree. As we traverse down, We go left and push all the
   * left nodes first in the stack. Once we reach to the bottom, we
   * store the node value and traverse right.
   *           1
   *         /   \
   *        2     3    preorder traversal: 4 -> 2 -> 5 -> 1 -> 6 -> 3
   *       / \   /     (left -> root -> right)
   *      4   5 6
   */
var inorderTraversal = function (root) {
  // In-Order Traversal ->
  //  1. Recursively traverse through the left subtree
  //  2. Visit current node
  //  3. Recursively traverse through the right subtree

  // Initialize array of values
  let result = [];

  // Recursive function to traverse through subtrees
  inorder(root, result);

  return result;
};

const inorder = (node, result) => {
  if (node === null) {
    return null;
  }
  inorder(node.left, result); // Traverse through left subtree
  result.push(node.val); // Visit node
  inorder(node.right, result); // Traverse through right subtree
};


Enter fullscreen mode Exit fullscreen mode

Top comments (0)