NUHMAN.com

Introduction

In this problem, we’re asked to perform a preorder traversal on a binary tree. Preorder traversal visits nodes in the order:

Root → Left → Right

This is a fundamental tree traversal algorithm and can be implemented recursively or iteratively.

Problem Statement

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example

Input:

markdown

    1
     \
      2
     /
    3

Output:

csharp

[1, 2, 3]

Approach 1: Recursive DFS

• Visit root
• Traverse left
• Traverse right

Go Implementation (Recursive)

go

package main

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
    var result []int
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        result = append(result, node.Val)
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return result
}

Approach 2: Iterative Using Stack

Mimic the recursive behavior using a stack:

1. Push root to stack.
2. While stack is not empty:

• Pop a node and add its value.
• Push right child first, then left child.

Go Implementation (Iterative)

go

func preorderTraversalIterative(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    stack := []*TreeNode{root}
    result := []int{}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, node.Val)

        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }

    return result
}

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(n) worst-case

• n is the number of nodes.
• Space is used by recursion stack or the explicit stack.

Use Cases

• Useful in scenarios where processing starts at the root before visiting children.
• Helpful in serialization of binary trees.

Conclusion

Binary Tree Preorder Traversal is a staple algorithm and serves as a stepping stone for more complex tree-based challenges. Mastering both the recursive and iterative versions prepares you for real-world problems involving tree structures and traversal patterns.