Skip to main content

Posts

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   1Strategy: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 leafPath 1 : 4 2 1Path 2: 4 2 3Path 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 subtre…

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   3Root-to-leaf paths:
   path 1: 4 2 1
   path 2: 4 2 3
   path 3: 4 5You 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.L…

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 (curre…

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. Implementationusing 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;…