Binary tree traversals

Traversing a binary tree involves iterating over all nodes in some order.

A tree node is represented like this:

    public class TreeNode
    {
        public int Value;
        public TreeNode Left;
        public TreeNode Right;
    
        public TreeNode(int value)
        {
            Value = value;
        }
    }

Binary tree example

Here are some traversals:

• Inorder (Left, Root, Right): 5, 4, 7, 2, 3, 6
• Preorder (Root, Left, Right): 2, 4, 5, 7, 3, 6
• Postorder (Left, Right, Root): 5, 7, 4, 6, 3, 2

Inorder

• Visit the left subtree
• Visit the root
• Visit the right-subtree

    public void InorderTraversal(TreeNode root)
    {
        if (root == null)
        {
            return;
        }

        InorderTraversal(root.Left);
        Console.WriteLine(root.Value);
        InorderTraversal(root.Right);
    }

Output: 5, 4, 7, 2, 3, 6

Time Complexity: O(n)

Preorder

• Visit the root
• Visit the left subtree
• Visit the right subtree

    public void PreorderTraversal(TreeNode root)
    {
        if (root == null)
        {
            return;
        }

        Console.WriteLine(root.Value);
        PreorderTraversal(root.Left);
        PreorderTraversal(root.Right);
    }

Output: 2, 4, 5, 7, 3, 6

Time Complexity: O(n)

Postorder

• Visit the left subtree
• Visit the right subtree
• Visit the root

    public void PostorderTraversal(TreeNode root)
    {
        if (root == null)
        {
            return;
        }

        PostorderTraversal(root.Left);
        PostorderTraversal(root.Right);
        Console.WriteLine(root.Value);
    }

Output: 5, 7, 4, 6, 3, 2

Time Complexity: O(n)

Video Lesson