Search⌘ K
AI Features
Home
Courses
Big-O Notation For Coding Interviews and Beyond

Tree Structures

Learn to analyze the time and space complexity involved with tree structures in algorithms. Understand traversal methods like pre-order, in-order, post-order, and depth-first search, and how recursion and stacks affect space. Discover how tree height influences performance, the difference between binary trees and binary search trees, and how implementation choices affect efficiency.

We'll cover the following...

In this lesson we won't attempt to describe various tree data-structures and their associated operations. Rather, we'll do a general discussion on how to reason and think about space and time complexity when tree structures are involved.

Tree Traversals

When traversing a tree, does the size of the tree affect how much time it takes for you to go through every node of the tree? Yes, it does. A bigger tree will take more time to go through than a smaller tree. The following recursive algorithms for tree traversals all take O(n) time since we are required to visit each node.

  • pre-order traversal

  • in-order traversal

  • post-order traversal

  • depth first search. Note the above three algorithms are types of depth first traversals

  • breadth first traversal/search

For the above algorithms, the more interesting question pertains to space complexity for the above algorithms. Since one can write these algorithms recursively, it's not immediately clear what the space complexity is. A novice may think it is constant when it is not. Look at the code below:

    class TreeNode {
        TreeNode left;
        TreeNode right;
        int val;
    }

    void recursiveDepthFirstTraversal(TreeNode root) {
        if (root == null)
            return;

        recursiveDepthFirstTraversal(root.left);
        System.out.println(root.val);
        recursiveDepthFirstTraversal(root.right);
    }

A naive look at the ...