Binary Tree Inorder Traversal
- 1 min read
- Tree
- Stack
- LC-Easy
- Binary Tree
- Depth First Search
3 years ago
Approach 1: Recursion
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
nodes = []
self.inorder(root, nodes)
return nodes
def inorder(self, root: Optional[TreeNode], nodes: List[int]):
if root:
self.inorder(root.left, nodes)
nodes.append(root.val)
self.inorder(root.right, nodes)
Approach 2: Iterative
- Inorder is
left -> root -> right - Use a stack and traverse left until you reach the end, keep adding nodes as you go
- Once you reach the end, pop the last node and add it to the result
- Then traverse the right node from the current node
- It's easier if you look at the code lmao just understand from there, hope the future me doesn't regret not explaining further.
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
nodes, stack = [], []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
nodes.append(node.val)
node = node.right
return nodes