Description
Given a binary tree, return the inorder traversal of its nodes’ values. Here the inorder means [left root right]. LeetCode here.
Recursive Solution
It’s quite easy, we jump to the code.
def Inorder_rec(root):
output = []
def helper(Node):
if Node.left:
helper(Node.left)
output.append(Node.val)
if Node.right:
helper(Node.right)
helper(root)
print(output)
Iterative Solution
We need a stack to save the traversed nodes. All elements in the stack should satisfy the following condition:
- The left child (if exist) of the node is traversed.
- The node value has not been saved to output list.
- the right child (if exist) of the node is not traversed. Go through the left child until it donot have left child. Then go back to its parent node by popping from the stack. Save the value of the parent node. Then go to the right child of the parent node. if right child not exist, pop parent node from the stack and do the same things as before until find a parent which has right child.
Then when should we stop? Shall we stop when the satck is empty? Not exactly true. Remember that when you go back to the root, the stack is empty but you have not checked the right child of the root yet. So the stop condition should be:
- The stack is empty.
- The current Node donot have right child.
def Inorder(Node):
if not Node:
return []
output = []
Now = Node
traveled = [Now]
while True:
while Now.left:
Now = Now.left
traveled.append(Now)
output.append(Now.val)
traveled.pop(-1)
if Now.right:
Now = Now.right
traveled.append(Now)
else:
try:
while not Now.right:
Now = traveled.pop(-1)
output.append(Now.val)
Now = Now.right
traveled.append(Now)
except IndexError:
print(output)
return
Similar Problem: LeetCode 145 Binary Tree Postorder Traversal
And here is another similar question for you: Binary Tree Preorder Traversal. LeetCode here.