The Yiki

Tree Traversal

4 min read

Given a binary tree, there are a couple ways to traverse the tree, each visiting nodes in a different order. All traversal algorithms have time and space complexity. (Or not???)

Pre-Order Traversal

Recursive Implementation

def preorder(root: Optional[None]):
	if root is None:
		return
    visit(root)
    preorder(root.left)
    preorder(root.right)

Iterative Implementation

def preorder(root: Optional[None]):
	st = [root]
	while st:
		node = st.pop()
		visit(node)
		
		if node is None:
			continue
		st.append(node.right)
		st.append(node.left)

Post-Order Traversal

Recursive Implementation

def postorder(root: Optional[None]):
	if root is None:
		return
    postorder(root.left)
    postorder(root.right)
    visit(root)

Iterative Implementation

def postorder(root: Optional[None]):
	st = []
	node = root
	lastNode = None
	
	while st or node:
		if node:
			st.append(node)
			node = node.left
		else:
			top = st[-1]
			if top.right and top.right != lastNode:
				node = top.right
			else:
				visit(top)	
				st.pop()
				lastNode = top

In-Order Traversal

Recursive Implementation

def inorder(root: Optional[None]):
	if root is None:
		return
    inorder(root.left)
    visit(root)
    inorder(root.right)
def inorder(root: Optional[None]):
	st = []
	node = root
	
	while st or node:
		if node:
			st.append(node)
			node = node.left
		else:
			node = st.pop()
			visit(node)
			node = node.right

Morris In-Order Traversal

Morris traversal is a traversal technique that results in in-order traversal but does not rely on any stack or recursion to run. Instead, it temporarily modifies the tree in-place. This way, it achieves space complexity while keeping the same time complexity as other traversal algorithms.

It rewrites the tree into its threaded form such that an edge between the rightmost node of a node’s left subtree to the the node itself. It then continues doing so recursively for the node’s left node.

graph TB
    subgraph row1 [" "]
        subgraph S8 ["Step 8: Remove thread 1→2, process node 3"]
            A7((4)) --> B7((2))
            A7 --> C7((6))
            B7 --> D7((1))
            B7 --> E7((3))
            C7 --> F7((5))
            C7 --> G7((7))
            style E7 fill:#4caf50,stroke:#333,stroke-width:3px
            style B7 fill:#e0e0e0,stroke:#333,stroke-width:1px
        end
        
        subgraph S6 ["Step 6: Process node 1, follow thread"]
            A5((4)) --> B5((2))
            A5 --> C5((6))
            B5 --> D5((1))
            D5 -.->|thread| B5
            B5 --> E5((3))
            E5 -.->|thread| A5
            C5 --> F5((5))
            C5 --> G5((7))
            style D5 fill:#4caf50,stroke:#333,stroke-width:3px
            style B5 fill:#ffeb3b,stroke:#333,stroke-width:3px
        end
		
        subgraph S4 ["Step 4: Find predecessor of 2 (node 1)"]
            A3((4)) --> B3((2))
            A3 --> C3((6))
            B3 --> D3((1))
            B3 --> E3((3))
            E3 -.->|thread| A3
            C3 --> F3((5))
            C3 --> G3((7))
            style D3 fill:#ff9800,stroke:#333,stroke-width:3px
            style B3 fill:#ffeb3b,stroke:#333,stroke-width:3px
        end
		
        subgraph S2 ["Step 2: Find predecessor of 4 (node 3)"]
            A1((4)) --> B1((2))
            A1 --> C1((6))
            B1 --> D1((1))
            B1 --> E1((3))
            C1 --> F1((5))
            C1 --> G1((7))
            style E1 fill:#ff9800,stroke:#333,stroke-width:3px
            style A1 fill:#ffeb3b,stroke:#333,stroke-width:3px
        end
    end
    
    subgraph row2 [" "]
        subgraph S7 ["Step 7: Remove thread 3→4, process node 2"]
            A6((4)) --> B6((2))
            A6 --> C6((6))
            B6 --> D6((1))
            D6 -.->|thread| B6
            B6 --> E6((3))
            C6 --> F6((5))
            C6 --> G6((7))
            style B6 fill:#4caf50,stroke:#333,stroke-width:3px
            style A6 fill:#e0e0e0,stroke:#333,stroke-width:1px
        end
        
        subgraph S5 ["Step 5: Create thread 1→2, move to left"]
            A4((4)) --> B4((2))
            A4 --> C4((6))
            B4 --> D4((1))
            D4 -.->|thread| B4
            B4 --> E4((3))
            E4 -.->|thread| A4
            C4 --> F4((5))
            C4 --> G4((7))
            style D4 fill:#ffeb3b,stroke:#333,stroke-width:3px
        end
	
        subgraph S3 ["Step 3: Create thread 3→4, move to left"]
            A2((4)) --> B2((2))
            A2 --> C2((6))
            B2 --> D2((1))
            B2 --> E2((3))
            E2 -.->|thread| A2
            C2 --> F2((5))
            C2 --> G2((7))
            style B2 fill:#ffeb3b,stroke:#333,stroke-width:3px
        end
		
        subgraph S1 ["Step 1: Initial State - Current = 4"]
            A((4)) --> B((2))
            A --> C((6))
            B --> D((1))
            B --> E((3))
            C --> F((5))
            C --> G((7))
            style A fill:#ffeb3b,stroke:#333,stroke-width:3px
        end
    end
	
    style row1 fill:none,stroke:none
    style row2 fill:none,stroke:none

Implementation

def morris_inorder(root):
    current = root
    while current is not None:
        if current.left is None:
            visit(current.value)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right is not None and predecessor.right != current:
                predecessor = predecessor.right
 
            if predecessor.right is None:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                visit(current.value)
                current = current.right

Graph View

Backlinks