Preorder Traversal of a Binary Tree (LeetCode 28)

Programming Languages
1

Preorder Traversal of a Binary Tree (LeetCode 28)

Introduction

In this article, we will explore the concept of preorder traversal in a binary tree and implement it using both recursive and iterative approaches. We will also discuss the time and space complexity of these solutions.

Binary Tree Traversal

Before diving into the preorder traversal, let’s briefly discuss the concept of binary tree traversal. A binary tree is a tree data structure in which each node has at most two children (left child and right child). Traversal of a binary tree involves visiting each node in a specific order. There are three types of traversals:

  • Inorder Traversal: Left subtree, root, right subtree
  • Preorder Traversal: Root, left subtree, right subtree
  • Postorder Traversal: Left subtree, right subtree, root

Preorder Traversal

Preorder traversal involves visiting the root node first, followed by the left subtree, and then the right subtree.

Example

Consider the following binary tree:

    1
   / \
  2   3

The preorder traversal of this tree is [1, 2, 3].

Recursive Solution

We can solve this problem using a recursive approach. The idea is to visit the root node first, and then recursively visit the left and right subtrees.

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    List<Integer> list = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        if (root != null) {
            list.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return list;
    }
}

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

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

Iterative Solution

We can also solve this problem using an iterative approach. The idea is to use a stack to store the nodes to be visited.

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        if (root != null) {
            stack.push(root);
        }

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            list.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return list;
    }
}

Time and Space Complexity

The time complexity of both recursive and iterative solutions is O(n), where n is the number of nodes in the binary tree. The space complexity of the recursive solution is O(h), where h is the height of the binary tree, due to the recursive call stack. The space complexity of the iterative solution is O(n) in the worst case, when the tree is skewed to one side.