ProgramGuru.org

ProgramGuru.org

Preorder Traversal of a Binary Tree using Iteration

Visualization

Algorithm Steps

  1. Start with the root node of the binary tree.
  2. If the tree is empty, return an empty result.
  3. Initialize a stack and push the root node onto it.
  4. While the stack is not empty, pop a node from the stack and record its value.
  5. If the popped node has a right child, push it onto the stack.
  6. If the popped node has a left child, push it onto the stack.
  7. Repeat until the stack is empty. The recorded values form the preorder traversal.

Preorder Traversal of a Binary Tree using Iteration - Code Examples Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root):
    if not root:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

if __name__ == '__main__':
    # Construct binary tree:
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(preorderTraversal(root))