Sponsored
Sponsored
This approach uses recursion to traverse the binary tree. Inorder traversal involves visiting the left subtree, the root node, and then the right subtree. The base case for the recursion is to return if the current node is null.
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(n) due to the recursion stack.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7function inorderTraversal(root) {
8 const result = [];
9 const inorder = (node) => {
10 if (!node) return;
11 inorder(node.left);
12 result.push(node.val);
13 inorder(node.right);
14 };
15 inorder(root);
16 return result;
17}In JavaScript, an internal function inorder is defined. It is called recursively to build the result array in the order of left subtree, root node, and right subtree.
In this approach, we use a stack to perform an iterative inorder traversal. The stack is utilized to track the nodes to be visited. This method mimics the recursive behavior by explicitly using a stack to push left children until reaching a null entry, then processes the nodes and explores the right subtrees.
Time Complexity: O(n)
Space Complexity: O(n)
1
Python's solution uses lists to manage the stack of nodes in place of a recursive method. The traversal ensures all elements are processed correctly in the inorder sequence.