Binary Tree Inorder Traversal
EasyPrompt
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward and intuitive approach. The structure of the recursive algorithm directly mirrors the definition of an inorder traversal (Left, Root, Right). We create a helper function that is called recursively on the left child, then processes the current node, and finally is called on the right child.
Algorithm
The core idea of inorder traversal is to visit nodes in the order: Left Subtree, Root, Right Subtree. A recursive function naturally models this process.
- Define a helper function, let's say
inorderHelper(TreeNode node, List<Integer> result). - The base case for the recursion is when the
nodeisnull. In this case, we simply return. - If the node is not
null: a. Make a recursive call on the left child:inorderHelper(node.left, result). b. After the left subtree has been fully traversed, visit the current node by adding its value to the result list:result.add(node.val). c. Finally, make a recursive call on the right child:inorderHelper(node.right, result). - The main function initializes an empty list and calls the helper function with the root of the tree.
Walkthrough
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); inorderHelper(root, result); return result; } private void inorderHelper(TreeNode node, List<Integer> result) { if (node == null) { return; } // 1. Traverse the left subtree inorderHelper(node.left, result); // 2. Visit the root node result.add(node.val); // 3. Traverse the right subtree inorderHelper(node.right, result); }}Complexity
Time
O(N), where N is the number of nodes in the tree, because we visit each node exactly once.
Space
O(H), where H is the height of the tree. In the worst case of a skewed tree, this becomes O(N), where N is the number of nodes. In the best case of a balanced tree, it's O(log N). This space is used by the recursion call stack.
Trade-offs
Pros
The code is simple, clean, and easy to understand as it directly follows the definition of inorder traversal.
It requires minimal code to implement.
Cons
For very deep or skewed trees, this can lead to a
StackOverflowErrorbecause the depth of the recursion call stack can exceed its limit.The space used by the call stack is implicit and not directly controlled by the programmer.
To avoid the potential for stack overflow from deep recursion, we can perform the traversal iteratively using an explicit stack. This approach mimics the behavior of the recursion call stack. We keep pushing left children onto the stack until we can't go further left. Then, we pop a node, process it, and move to its right child.
Algorithm
This method simulates the recursive approach using an explicit stack to keep track of the nodes.
- Initialize an empty
List<Integer>for the result and an emptyStack<TreeNode>. - Create a
TreeNodepointer,current, and initialize it toroot. - Loop as long as
currentis notnullor thestackis not empty. - Inside the loop, push all the left children onto the stack: while
currentis notnull, pushcurrentto the stack and updatecurrenttocurrent.left. - Once
currentbecomesnull, it means we have reached the leftmost node of the current subtree. Now, we process the node at the top of the stack. - Pop a node from the stack, let this be the new
current. - Add the value of the popped node to the result list:
result.add(current.val). - Move to the right child of the popped node:
current = current.right. This will start the process for the right subtree in the next iteration of the main loop.
Walkthrough
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode current = root; while (current != null || !stack.isEmpty()) { // Go as far left as possible while (current != null) { stack.push(current); current = current.left; } // Backtrack from the empty subtree, visit the node at the top of the stack current = stack.pop(); result.add(current.val); // Now, visit the right subtree current = current.right; } return result; }}Complexity
Time
O(N), as each node is pushed onto and popped from the stack exactly once.
Space
O(H), where H is the height of the tree. In the worst case of a skewed tree, this becomes O(N). In the best case of a balanced tree, it's O(log N). This space is used by the explicit stack.
Trade-offs
Pros
It avoids recursion, thus eliminating the risk of a
StackOverflowErrorfor very deep trees.It can be more efficient in languages where function calls have high overhead.
Cons
The logic is slightly more complex to write and understand compared to the recursive version.
It still requires extra space for the stack, which can be significant for skewed trees.
This is the most space-efficient approach. The key idea is to create temporary links (or "threads") in the tree to keep track of where to go next, eliminating the need for a stack or recursion. For each node, we find its inorder predecessor (the rightmost node in its left subtree). We use the predecessor's right pointer (which would normally be null) to point back to the current node. This thread allows us to return to the current node after traversing its entire left subtree. Once we return, we visit the current node, remove the thread, and move to the right subtree.
Algorithm
Morris Traversal modifies the tree on the fly to create links (threads) to inorder successors, and then reverts the changes. This allows traversal without a stack or recursion.
- Initialize a
currentpointer torootand an empty listresult. - While
currentis notnull: a. Ifcurrenthas no left child: i. Visitcurrentby adding its value toresult. ii. Move to the right child:current = current.right. b. Ifcurrenthas a left child: i. Find the inorder predecessor ofcurrent. The predecessor is the rightmost node in the left subtree ofcurrent. Let's call itpre. ii. If the right child ofpreisnull(we haven't created a thread yet): - Create a thread frompretocurrent:pre.right = current. - Movecurrentto its left child to traverse the left subtree:current = current.left. iii. If the right child ofpreiscurrent(a thread exists, meaning we've finished traversing the left subtree): - Remove the thread to restore the tree's original structure:pre.right = null. - Visitcurrentby adding its value toresult. - Move to the right child:current = current.right.
Walkthrough
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); TreeNode current = root; TreeNode pre; while (current != null) { if (current.left == null) { result.add(current.val); // Visit node current = current.right; // Move to right } else { // Find the inorder predecessor of current pre = current.left; while (pre.right != null && pre.right != current) { pre = pre.right; } if (pre.right == null) { // Create the thread pre.right = current; current = current.left; } else { // Thread exists, so we've visited the left subtree // Remove the thread pre.right = null; result.add(current.val); // Visit node current = current.right; // Move to right } } } return result; }}Complexity
Time
O(N). Although we seem to traverse some parts of the tree multiple times, a closer analysis shows that each edge is traversed at most twice (once to go down, and once to come back up via the thread). Therefore, the total time complexity is linear.
Space
O(1). No extra space is used besides a few pointers to traverse the tree.
Trade-offs
Pros
Extremely space-efficient, achieving O(1) auxiliary space.
It does not use recursion, so there is no risk of stack overflow.
Cons
The algorithm is much more complex to understand and implement correctly.
It temporarily modifies the tree structure. This can be problematic in a multi-threaded environment if the tree is shared, as it would require locking mechanisms.
Solutions
Solution
import java.util.ArrayList ; import java.util.HashSet ; import java.util.List ; import java.util.Stack ; public class Binary_Tree_Inorder_Traversal { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution_optmize { public List < Integer > inorderTraversal ( TreeNode root ) { List < Integer > list = new ArrayList < Integer >(); if ( root == null ) { return list ; } Stack < TreeNode > sk = new Stack <>(); TreeNode current = root ; while (! sk . isEmpty () || current != null ) { while ( current != null ) { sk . push ( current ); current = current . left ; } // @note: 一逼撸到最左边 // @note: 没有push left的操作，就不会无限循环，也不需要mark是否visited TreeNode leftOrMiddle = sk . pop (); list . add ( leftOrMiddle . val ); current = leftOrMiddle . right ; // if right is null here, next time pop parent node } return list ; } } class Solution_noStack { // but modifying original tree public List < Integer > inorderTraversal ( TreeNode root ) { List < Integer > result = new ArrayList <>(); TreeNode current = root ; TreeNode prev ; while ( current != null ) { if ( current . left == null ) { result . add ( current . val ); // only handle right child current = current . right ; // move to next right node } else { // has a left subtree prev = current . left ; while ( prev . right != null ) { // find rightmost prev = prev . right ; } prev . right = current ; // put cur after the pre node TreeNode temp = current ; // store cur node current = current . left ; // move cur to the top of the new tree temp . left = null ; // original cur left be null, avoid infinite loops } } return result ; } } public class Solution { List < Integer > list = new ArrayList < Integer >(); public List < Integer > inorderTraversal ( TreeNode root ) { // mark if a node is visited already: true is visited. or, just use a Set HashSet < TreeNode > hs = new HashSet <>(); Stack < TreeNode > sk = new Stack <>(); sk . push ( root ); while (! sk . isEmpty ()) { TreeNode current = sk . pop (); if ( current == null ) { continue ; } // @note: careful to check left visited, or else infinite looping if ( current . left != null && ! hs . contains ( current . left )) { sk . push ( current ); sk . push ( current . left ); } else { if ( current . right != null && ! hs . contains ( current . right )) { sk . push ( current . right ); } hs . add ( current ); list . add ( current . val ); } } return list ; } } class Solution_recursion { List < Integer > result = new ArrayList <>(); public List < Integer > inorderTraversal ( TreeNode root ) { dfs ( root ); return result ; } public void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); result . add ( root . val ); dfs ( root . right ); } } } ////// /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List < Integer > inorderTraversal ( TreeNode root ) { List < Integer > ans = new ArrayList <>(); while ( root != null ) { if ( root . left == null ) { ans . add ( root . val ); root = root . right ; } else { TreeNode prev = root . left ; while ( prev . right != null && prev . right != root ) { prev = prev . right ; } if ( prev . right == null ) { prev . right = root ; root = root . left ; } else { ans . add ( root . val ); prev . right = null ; root = root . right ; } } } return ans ; } }/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ var inorderTraversal = function (root) { let ans = []; while (root) { if (!root.left) { ans.push(root.val); root = root.right; } else { let prev = root.left; while (prev.right && prev.right != root) { prev = prev.right; } if (!prev.right) { prev.right = root; root = root.left; } else { ans.push(root.val); prev.right = null; root = root.right; } } } return ans; };/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector < int > inorderTraversal ( TreeNode * root ) { vector < int > ans ; while ( root ) { if ( ! root -> left ) { ans . push_back ( root -> val ); root = root -> right ; } else { TreeNode * prev = root -> left ; while ( prev -> right && prev -> right != root ) { prev = prev -> right ; } if ( ! prev -> right ) { prev -> right = root ; root = root -> left ; } else { ans . push_back ( root -> val ); prev -> right = nullptr ; root = root -> right ; } } } return ans ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def inorderTraversal ( self , root : Optional [ TreeNode ]) -> List [ int ]: stack = [] current = root res = [] while stack or current : while current : stack . append ( current ) current = current . left left_or_middle = stack . pop () res . append ( left_or_middle . val ) current = left_or_middle . right return res # no stack, but modifying original tree class Solution : def inorderTraversal ( self , root ): result = [] current = root prev = None while current : if current . left is None : result . append ( current . val ) current = current . right else : prev = current . left while prev . right : prev = prev . right prev . right = current temp = current current = current . left temp . left = None return result class Solution : def inorderTraversal ( self , root : Optional [ TreeNode ]) -> List [ int ]: ans = [] while root : if root . left is None : ans . append ( root . val ) root = root . right else : prev = root . left while prev . right and prev . right != root : prev = prev . right if prev . right is None : prev . right = root root = root . left else : ans . append ( root . val ) prev . right = None root = root . right return ans ########### # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None ''' >>> stack = [(1, None)] >>> stack.extend([(0, None), (2, "b"), (3, "c")]) >>> stack [(1, None), (0, None), (2, 'b'), (3, 'c')] ''' class Solution ( object ): def inorderTraversal ( self , root ): """ :type root: TreeNode :rtype: List[int] """ # stack to hold tuple (), '0' meaning a parent node for current level, '1' meaning a child node res , stack = [], [( 1 , root )] while stack : p = stack . pop () if not p [ 1 ]: continue stack . extend ([( 1 , p [ 1 ]. right ), ( 0 , p [ 1 ]), ( 1 , p [ 1 ]. left )]) if p [ 0 ] != 0 else res . append ( p [ 1 ]. val ) return resVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.