Data Structures & Algorithms - Binary Tree Traversals

Binary Tree Traversals

A binary tree can be traversed depth-first or breadth-first order. There are 3 ways to traverse in depth-first order: in-order, pre-order and post-order. There is 1 way to traverse in breadth-first order: level-order (which requires the use of a queue data structure).

Consider the following binary tree and the various methods of traversal.

      1
     / \         InOrder: 4 2 5 1 3
    /   \       PreOrder: 1 2 4 5 3
   2     3     PostOrder: 4 5 2 3 1
  / \         LevelOrder: 1 2 3 4 5
 4   5

public class Program
{
    public static void Main(string[] args)
    {
        //      1
        //     / \
        //    /   \
        //   2     3
        //  / \
        // 4   5

        TreeNode t5 = new TreeNode(5, null, null);
        TreeNode t4 = new TreeNode(4, null, null);
        TreeNode t3 = new TreeNode(3, null, null);
        TreeNode t2 = new TreeNode(2, t4, t5);
        TreeNode t1 = new TreeNode(1, t2, t3);

        Console.Write("   InOrder: ");
        InOrder(t1);
        Console.WriteLine();

        Console.Write("  PreOrder: ");
        PreOrder(t1);
        Console.WriteLine();

        Console.Write(" PostOrder: ");
        PostOrder(t1);
        Console.WriteLine();

        Console.Write("LevelOrder: ");
        LevelOrder(t1);
        Console.WriteLine();
    }

    public static void InOrder(TreeNode n)
    {
        if (n != null)
        {
            InOrder(n.Left);
            Console.Write(n.Data + " ");
            InOrder(n.Right);
        }
    }

    public static void PreOrder(TreeNode n)
    {
        if (n != null)
        {
            Console.Write(n.Data + " ");
            PreOrder(n.Left);
            PreOrder(n.Right);
        }
    }

    public static void PostOrder(TreeNode n)
    {
        if (n != null)
        {
            PostOrder(n.Left);
            PostOrder(n.Right);
            Console.Write(n.Data + " ");
        }
    }

    public static void LevelOrder(TreeNode n)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        if (n != null)
        {
            queue.Enqueue(n);
        }
        while (queue.Count > 0)
        {
            TreeNode node = queue.Dequeue();
            Console.Write(node.Data + " ");
            if (node.Left != null)
            {
                queue.Enqueue(node.Left);
            }
            if (node.Right != null)
            {
                queue.Enqueue(node.Right);
            }
        }
    }
}

public class TreeNode
{
    public int Data;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int data, TreeNode left, TreeNode right)
    {
        Data = data;
        Left = left;
        Right = right;
    }
}


© 2020 | Paul Kim