Given a binary tree, print the nodes from left to right when it is seen from bottom. Given an example below:

If we look the tree from bottom we will be able to see 5, 15, 25 but we could see either 18 or 22 since overlapping on same height and we will not be able to see root 20 because 18 and 22 are in front of the root. So our solution will be 5, 15, 18, 25 or 5, 15, 22, 25.

Solution

If we consider root is the origin (0, 0) and try to allocate x and y coordinates to each node the picture will be as shown below:

Now we can see we have to pick node's in output which has highest height at each width. So we iterate each node starting from root, left nodes will have decrement in width by one from it's parent and right side of nodes will have increment in width by one from it's parent but height will be increasing by one in each iteration. Now let's write the code:

public class HashObject
{
    public int Height { get; set; }
    public BinarySearchTree.Node Node { get; set; }
}

Above a class stores a node with it's height.

/// <summary>
/// Traversing
/// </summary>
/// <param name="node">tree node</param>
/// <param name="dict">dictionary to hold lowest node at each width</param>
/// <param name="width">width from root</param>
/// <param name="height">height from root</param>
/// <returns></returns>
static Dictionary<int, HashObject> Traverse(BinarySearchTree.Node node, Dictionary<int, HashObject> dict, int width, int height)
{
    if (node != null)
    {
        //left side width will decrese by one from root, but hieght always increases
        Traverse(node.Left, dict, width - 1, height + 1);
        if (!dict.ContainsKey(width))
        {
            dict.Add(width, new HashObject{ Height = height, Node = node});
        }
        else
        {
            //if stored height is less than current height at particular width
            if (dict[width].Height < height)
                dict[width].Node = node;
        }
        //right side width will increase by one from root, but hieght always increases
        Traverse(node.Right, dict, width + 1, height + 1);
    }
    return dict;
}

Above method uses in-order traversal and inserting node with highest height at each width. We used dictionary's key as tree's height to make sure only one key is present for a particular width.

static void Main(string[] args)
{
    //building tree
    IBinerySearchTree bst = new BinerySearchTree();
    bst.Insert(new Node() { Key = 20 });
    bst.Insert(new Node() { Key = 15 });
    bst.Insert(new Node() { Key = 18 });
    bst.Insert(new Node() { Key = 25 });
    bst.Insert(new Node() { Key = 22 });
    bst.Insert(new Node() { Key = 5 });
           
    Dictionary<int, HashObject> dict = new Dictionary<int, HashObject>();
    dict = Traverse(bst.Root, dict, 0, 0);
    //printing result
    dict.ToList().ForEach(x => { Console.WriteLine(x.Value.Node.Key); });
    Console.ReadLine();
}

Output:

5
15
18
25