Given the root of a binary tree, return the values of its nodes in inorder: first the left subtree, then the node itself, then the right subtree.
Example 1
Input: root = [1,null,2,3]
Output: [1,3,2]
Node 1 has no left child, so it comes first; then the subtree of 2 gives 3 before 2.
Example 2
Input: root = []
Output: []
Constraints
- The number of nodes is in the range 0 to 100
- -100 <= Node.val <= 100
Hints
Frequently asked at: Amazon, Microsoft, TCS, Infosys, Wipro
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The recursive solution is natural and O(n), but interviewers usually want the iterative one because it shows you understand the call stack. Recursion goes as far left as possible, records a node on the way back, then explores its right side. We can copy that exactly with an explicit stack: push nodes while walking left, and when the walk ends, the top of the stack is the next node in inorder.
Algorithm
- Start with
cur = rootand an empty stack. - While
curis not null or the stack is not empty: pushcurand movecur = cur.leftuntil it is null. - Pop a node, append its value to the answer.
- Set
curto that node's right child and repeat.
Time:
O(n)Space: O(h), where h is the height of the treeInterview tip: A common follow-up is O(1) extra space: Morris traversal temporarily links each node's inorder predecessor back to it, then removes the link.
class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: res, stack = [], [] cur = root while cur or stack: while cur: # go as far left as possible stack.append(cur) cur = cur.left cur = stack.pop() # next node in inorder res.append(cur.val) cur = cur.right # then explore its right subtree return resCtrl + Enter runs the examples