Yong's Blog
0%

binary tree traversal [updated]

Posted on Edited on In Views: Valine:

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