0%

binary tree traversal [updated]

I wrote post Binary_Tree_Traversal around two years ago to help me remember how to traversal binary tree iteratively.
The solution in that post is quite simply. But I still have trouble to remember it since the code pattern is slight different within preorder, inorder, postorder.

Eventually, I rewrite the code using similar pattern in python.

preorder

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def preorderTraversal(self, root):
rst, stack = [], []
cur = root
while cur or stack:
while cur:
rst.append(cur.val)
stack.append(cur.right)
cur = cur.left
cur = stack.pop()
return rst

inorder

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
rst, stack = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
rst.append(cur.val)
cur = cur.right
return rst

postorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
rst, stack = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left or cur.right
cur = stack.pop()
rst.append(cur.val)
if stack and stack[-1].left == cur:
cur = stack[-1].right
else:
cur = None
return rst