Binary Tree Traversal

Binary Tree Node

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

1. DFS

1.1 Preorder

Visit root first -> traverse left subtree -> traverse right subtree

Order: 2, 7, 2, 6, 5, 11, 5, 9, 4

• Recursive: O(N), O(1)

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        res = []
        res += [root.val]
        res += self.preorderTraversal(root.left)
        res += self.preorderTraversal(root.right)
        
        return res

• Iterative: O(N), O(N)

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        res = []
        stack = [root]
        
        while stack:
            cur = stack.pop()
            
            res.append(cur.val)
            if cur.right:
                stack.append(cur.right)
            if cur.left:
                stack.append(cur.left)
        
        return res

1.2 Inorder

Traverse left subtree -> visit root -> traverse right subtree

Result: 2, 7, 5, 6, 11, 2, 5, 4, 9

• Recursive: O(N), O(1)

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        res = []
        res += self.inorderTraversal(root.left)
        res += [root.val]
        res += self.inorderTraversal(root.right)
        
        return res

• Iterative: O(N), O(N)

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        res = []
        
        stack = []
        current = root
        
        while True:
            if current:
                stack.append(current)
                current = current.left
            else:
                if stack:
                    current = stack.pop()
                    res.append(current.val)
                    current = current.right
                else:
                    break
        
        return res

1.3 Postorder

Traverse left subtree -> traverse right subtree -> visit root

Result: 2, 5, 11, 6, 7, 4, 9, 5, 2

• Recursive: O(N), O(1)

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        res = []
        
        res += self.postorderTraversal(root.left)
        res += self.postorderTraversal(root.right)
        res += [root.val]
        
        return res

• Iterative: O(N), O(N)

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        res = []
        
        stack = [root]
        
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            
            if cur.left:
                stack.append(cur.left)
            if cur.right:
                stack.append(cur.right)
        
        return res[::-1]

2. BFS

Breadth first serch traverse trees level by level.

Result: 2, 7, 5, 2, 6, 9, 5, 11, 4

• Iteravite: O(N), O(N)

from collections import deque

class Solution:
    def bfs(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        res = []
        
        queue = deque()
        queue.appendleft(root)
        
        while queue:
            cur = queue.pop()
            res.append(cur.val)
                
            if cur.left:
                queue.appendleft(cur.left)
                
            if cur.right:
                queue.appendleft(cur.right)
        
        return res

3. Example

This is a good example how to solve a problem by applying a combination of these strategies.

Leetcode 545: Boundary of Binary Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def boundaryOfBinaryTree(self, root: TreeNode) -> List[int]:
        """
        get left most nodes - O(n / 2)
        get all leaves - O(n)
        get right most nodes O(n / 2)
        """
        if not root: return []
        res = [root.val]
        
        def leftBoundary(subroot):
            """
            preorder
            traverse left subtree, if left subtree doesn't exist then go to right subtree
            base case: if root is empty or if root is a leaf node
            """
            if subroot is None or subroot.left is None and subroot.right is None: return
            res.append(subroot.val)
            if subroot.left:
                leftBoundary(subroot.left)
            else:
                leftBoundary(subroot.right)
        
        def rightBoundary(subroot):
            """
            postorder
            traverse right subtree, if right subtree doesn't exist then go to left subtree
            base case: if root is empty or if root is a leaf node
            """
            if not subroot or not subroot.left and not subroot.right: return
            if subroot.right:
                rightBoundary(subroot.right)
            else:
                rightBoundary(subroot.left)
            res.append(subroot.val)
        
        def getLeaves(node):
            """
            DFS, preorder
            """
            if not node: return
            if not node.left and not node.right and node != root:
                res.append(node.val)
            
            getLeaves(node.left)
            getLeaves(node.right)
            
        leftBoundary(root.left)
        getLeaves(root)
        rightBoundary(root.right)
        return res