Return the inorder traversal of a binary tree. Inorder means left subtree first, then the node, then the right subtree.
DSA Animator › DSA Revision › Tree › Binary Tree Inorder Traversal
Remember: go left as far as you can, pop, record, then go right. Inorder of a binary search tree is sorted. The video solves Binary Tree Inorder Traversal (LeetCode 94, Easy) with the Inorder with Stack pattern from the Tree topic, and you can replay every step in the interactive Binary Tree Inorder Traversal animation.
Return the inorder traversal of a binary tree. Inorder means left subtree first, then the node, then the right subtree.
For the tree 4, with children 2 and 6, and grandchildren 1, 3, 5, 7, the inorder is 1 to 7. For a binary search tree, inorder always gives the values in sorted order.
The recursive version is only three lines, but the interviewer often asks for the iterative one. The iterative version uses an explicit stack in place of the call stack.
Start at the root, and keep going left, pushing every node on the stack. When you cannot go left any more, pop the top node and record it. Then move to its right child, and repeat the same process from there. Stop when the current node is null and the stack is empty.
Push 4, then 2, then 1, going left as far as possible. 1 has no left child, so pop and record 1, and its right is empty. Pop and record 2, then move to its right child, 3. Push 3, pop it and record 3. Pop and record 4, then move right to 6. Push 6 and 5, then record 5, 6, and finally 7. The inorder is 1, 2, 3, 4, 5, 6, 7.
In code, loop while the current node is not null or the stack is not empty. While current is not null, push it and move left. Then pop a node, add its value, and set current to its right child. Each node is pushed and popped once, so it's O of n time and O of the height in space.
Remember: go left as far as you can, pop, record, then go right. Inorder of a binary search tree is sorted.