Problem : Given the following binary tree, print all the paths from root node to all the leave nodes.

Output :

• 20 –> 9 –> 5
• 20 –> 9 –> 12 –> 15
• 20 –> 49 –> 23
• 20 –> 49 –> 52 –> 50

Solution :

The output clearly highlights the fact that a depth first traversal of the tree will get us the desired out. Important thing to note here is that, a given node is not marked as visited unless until all of its left & right child tree nodes have been visited i.e. a node that gets selected first will be the last one to be marked as visited(FILO – first in last out) or in other words, a node that is selected last will be the first one to be marked as visited(LIFO).

Steps:

• Node structure to have “isVisited” boolean property defaulted to false. Once all of the child nodes are visited, isVisited flag will be set to true.
• For traversal & back-tracking support, we will make use of Stack data structure. The implementation & its usage is self explanatory from the code given below.

Code

void Main()
{
    Node n20 = new Node(20);
    n20.Left = new Node(9);
    n20.Left.Left = new Node(5);
    n20.Left.Right = new Node(12);
    n20.Left.Right.Right = new Node(15);
    n20.Right = new Node(49);
    n20.Right.Left = new Node(23);
    n20.Right.Right = new Node(52);
    n20.Right.Right.Left = new Node(50);
    
    PrintPath(n20);
}

public class Node
{
    public Node Left {get; set;}
    public Node Right {get; set;}
    public bool IsVisited {get; set;}
    public int Value {get;set;}
    
    public Node(int value)
    {
        this.Value = value;
    }
}

public static bool IsLeaveElement(Node node)
{
    if(node == null) return false;
    if(node.Left == null && node.Right == null) return true;
    return false;
}

public static void PrintPath(Node node)
{
    Stack<Node> stack = new Stack<Node>();
    stack.Push(node);
    
    while(stack.Count != 0)
    {
        Node item = stack.Peek();
        
        if(!item.IsVisited) {
            Node tempLeft = item.Left;
            if(tempLeft != null && !tempLeft.IsVisited)
            {
                stack.Push(tempLeft);
                continue;
            }
            
            Node tempRight = item.Right;
            if(tempRight != null && !tempRight.IsVisited) {
                stack.Push(tempRight);
                continue;
            }
            
            item.IsVisited = true;
        }
        else {
            item.IsVisited = true;
            if(IsLeaveElement(item)) {
                foreach(var value in stack) {
                    Console.Write(value.Value + " --> ");
                }
                Console.WriteLine();
            }
            stack.Pop();
        }
    }
}

Problem : Find the maximum depth in a given binary tree?

Output : 4 (20 –> 9 –> 12 –> 15)

Solution : If we consider the root node as starting point, then maximum depth from root node is maximum of depth values from root left sub-tree & root right sub-tree.

Code

void Main()
{
    Node n20 = new Node(20);
    n20.Left = new Node(9);
    n20.Left.Left = new Node(5);
    n20.Left.Right = new Node(12);
    n20.Left.Right.Right = new Node(15);
    n20.Right = new Node(49);
    n20.Right.Left = new Node(23);
    n20.Right.Right = new Node(52);
    n20.Right.Right.Left = new Node(50);
    
    GetMaxDepth(n20).Dump();
}

public class Node
{
    public Node Left {get; set;}
    public Node Right {get; set;}
    public int Value {get;set;}
    
    public Node(int value)
    {
        this.Value = value;
    }
}

public static int GetMaxDepth(Node node)
{
    if(node == null) return 0;
    
    return Math.Max(1 + GetMaxDepth(node.Left), 1 + GetMaxDepth(node.Right));
}