Bottom-up level order traversal of a binary tree

Given a binary tree, return the bottom-up level order traversal of a binary tree. Nodes on the same level should be returned from left to right.

This problem very similar to level order traversal of a binary tree the only difference is level order.

 

 

Algorithm

We already know how to traverse a binary, the only difference is to traverse by level. During the traversal, we need to store a level of a node. The easiest way to do it is to use recursion.

 

 

To solve this problem we can use Preorder traversal algorithm:

• 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);
    }

The preorder traversal algorithm helps to sequence nodes from left to right and the only thing left is to store a node level. We can do it by adding an additional parameter in our recursion call.

Code

    public List<List<int>> LevelOrder(TreeNode root)
    {
        if (root == null)
        {
            return new List<List<int>>();
        }

        var result = new List<List<int>>();
        LevelOrderBottom(root, 0, result);
        return result;
    }

    private void LevelOrderBottom(TreeNode root, int level, List<List<int>> result)
    {
        if (root == null)
        {
            return;
        }

        if (level >= result.Count)
        {
            result.Insert(0, new List<int>());
        }

        // bottom-up level order
        result[result.Count - level - 1].Add(root.Value);

        LevelOrderBottom(root.Left, level + 1, result);
        LevelOrderBottom(root.Right, level + 1, result);
    }

Time Complexity: O(n)