Tree Structures

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 ...