Mirror of a binary tree

 

This is continuation of my post How to create binary tree in c#.In this post I will show you how convert a given binary tree into it’s mirror image.

/**
Changes the tree into its mirror image.

So the tree...
       4
      / \
     2   5
    / \
   1   3

is changed to...
       4
      / \
     5   2
        / \
       3   1

Strategy:Uses a recursive helper that recurs over the tree, swapping the left/right pointers.

 public void MirrorTree()
        {
            MirrorTree(_root);
        }

private void MirrorTree(Node node)
        {
            if (node != null)
            {
                // do the sub-trees 
                MirrorTree(node.Left);
                MirrorTree(node.Right);

                // swap the left/right pointers 
                Node temp = node.Left;
                node.Left = node.Right;
                node.Right = temp;
            }
 } 

How to print out all path from root to leaf of a given binary tree

This is continuation of my post How to create binary tree in c#.In this post I will show you how to print all path from root to leaf of a given binary tree in c#.Let’s consider following binary tree.

             *       4
             *    2     5
             *  1    3    

For above tree there are three path from root to leaf

Path 1 : 4 2 1

Path 2: 4 2 3

Path 3: 4 5

  public void PrintPath()
        {
            int[] path = new int[100];
            printPaths(_root, path, 0);
        }
        private void printPaths(Node node, int[] path, int pathLen)
        {
            if (node == null) return;

            // append this node to the path array 
            path[pathLen] = node.Data;
            pathLen++;

            // it's a leaf, so print the path that led to here 
            if (node.Left == null && node.Right == null)
            {
                PrintArray(path, pathLen);
            }
            else
            {
                // otherwise try both subtrees 
                printPaths(node.Left, path, pathLen);
                printPaths(node.Right, path, pathLen);
            }
        }

        private void PrintArray(int[] path, int pathLen)
        {
            for (int i = 0; i < pathLen; i++)
            {
                Console.Write(path[i] + " ");
            }
            Console.WriteLine();
        }

Given a binary tree, find path sum

Given a tree and a sum, returns true if there is a path from the root  down to a leaf, such that adding up all the values along the path  equals the given sum.let’s consider the following binary tree as an example and path sum value is 9.

       4
      / \
     2   5
    / \
   1   3

Root-to-leaf paths:
   path 1: 4 2 1
   path 2: 4 2 3
   path 3: 4 5

You can see that there are two path that gives sum 9 (Path2 and Path 3).Traverse the tree from root to leaves in top down fashion and subtract the node value from the sum  and check to see if the sum is 0 when you run out of tree.

 public bool HasPathSum(int sum)
        {
            return HasPathSum(_root, sum);
        }
        private bool HasPathSum(Node root, int sum)
        { 
            // return true if we run out of tree and sum==0 
            if (root == null)
                return sum == 0;
            else
            {
                int subSum = sum - root.Data;
                return (
                    HasPathSum(root.Left, subSum)
                    || HasPathSum(root.Right, subSum)
                    );
            }

        }


 

How to find min or max value in a given binary tree

This is continuation of my post How to create binary tree in c#.In this post I will show you how to find max or min value in a given binary tree.

Min Value: Loop down to find the leftmost leaf

Max Value: Loop down to find the rightmost leaf

     public int FindMinValue()
        {
            return FindMinValue(_root);
        }

        private int FindMinValue(Node root)
        {
            if (root == null)
                return -1;
            else
            {
                Node current = root;
                while (current.Left!=null)
                {
                    current = current.Left;
                }
                return current.Data;

            }
        }
        public int FindMaxValue()
        {
            return FindMaxValue(_root);

        }

        private int FindMaxValue(Node root)
        {
            if (_root == null)
                return -1;
            else
            {
                Node current = root;
                while (current.Right!=null)
                {
                    current = current.Right;
                }
                return current.Data;
            }
        }

How to calculate max depth of given binary tree in c#

This is continuation of my post How to create binary tree in c#.In this post I will show you how to calculate max depth of a given binary tree in c#.

MaxDepth of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node.

  public int MaxDepth()
        {
            return MaxDepth(_root);
        }
        private int MaxDepth(Node root)
        {
            if (root == null)
                return -1;
            // compute the depth of each subtree 
            else
            {
                int leftDepth = MaxDepth(root.Left);
                int rightDepth = MaxDepth(root.Right);
                //Return max of left or right tree.
                return 1 + Math.Max(leftDepth, rightDepth);
            }
        }

How to calculate size of binary tree

This is continuation of my post How to create binary tree in c# .In this post I will show you how to find size of binary tree.Size of binary tree is number of nodes in a given tree.

Following is the recursive implementation of size function

  //Compute the number of nodes in a tree. 
        public int Size()
        {
            return Size(_root);
        }
        private int Size(Node root)
        {
            if (root == null)
                return 0;
            return 1 + Size(root.Left) + Size(root.Right);
        }

How to create binary tree in c#

A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

download

Implementation

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BTree
{
    public class Node
    {
        public int Data { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
        public Node()
        {

        }
        public Node(int data)
        {
            this.Data = data;

        }
    }
    public class BinaryTree
    {
        private Node _root;
        public BinaryTree()
        {
            _root = null;
        }
        public void Insert(int data)
        {
            // 1. If the tree is empty, return a new, single node 
            if (_root == null)
            {
                _root = new Node(data);
                return;
            }
            // 2. Otherwise, recur down the tree 
            InsertRec(_root, new Node(data));
        }
        private void InsertRec(Node root, Node newNode)
        {
            if (root == null)
                root = newNode;

            if (newNode.Data < root.Data)
            {
                if (root.Left == null)
                    root.Left = newNode;
                else
                    InsertRec(root.Left, newNode);

            }
            else
            {
                if (root.Right == null)
                    root.Right = newNode;
                else
                    InsertRec(root.Right, newNode);
            }
        }
        private void DisplayTree(Node root)
        {
            if (root == null) return;

            DisplayTree(root.Left);
            System.Console.Write(root.Data + " ");
            DisplayTree(root.Right);
        }
        public void DisplayTree()
        {
            DisplayTree(_root);
        }

    }

    class Program
    {
        static void Main(string[] args)
        {
            BinaryTree tree = new BinaryTree();
            Node root = new Node();

            tree.Insert(4);
            tree.Insert(2);
            tree.Insert(5);
            tree.Insert(1);
            tree.Insert(3);
            tree.DisplayTree();
        }
    }
}