Print nodes in top view of binary tree

Printing of the top view of given tree that is one of the challenging problem of tree. We can solve this problem in many ways. Let see the possibility to print top view of tree.

First possibility : Get the head node of tree and print that element. After that if head node left subtree are exist then print top element of that nodes from top to bottom. Similar way if exist root node right subtree then print that elements form bottom to top.

Print Top view of Tree

In this example {1} is root element and {2 4 7} is left sub tree top view elements and {3 6 10} is top elements of right subtree. We can solve this problem by using recursion.

Here given code implementation process.

/*
  C Program 
  Print Top View of Binary Tree using Recursion
*/
#include<stdio.h>
#include<stdlib.h>
//structure of Binary Tree node
struct Node{
  int data;
  struct Node*left,*right;
};


//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes
struct Node* insert(int data){
  //create dynamic memory to new binary tree node
  struct Node*new_node=(struct Node*)malloc(sizeof(struct Node));
  if(new_node!=NULL){
    //set data and pointer values
    new_node->data=data;
    new_node->left=NULL; //Initially node left-pointer is NULL
    new_node->right=NULL;//Initially node right-pointer is NULL
  }else{
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  //return reference
  return new_node;
  
}

//Print tree node in left view 
void left_top(struct Node*node,int *left_part,int height){

  if(node==NULL){
    return;
  }

  if(*left_part<height){
    //Get printed node
    *left_part+=1;
    //That is left view node
    printf("%d  ",node->data);
  }
  //Recursive call
  left_top(node->left,left_part,height+1);
  left_top(node->right,left_part,height-1);

}

//Print right view nodes of tree from top to bottom elements
void right_top(struct Node*node,int *right_part,int height){

  if(node==NULL){
    return;
  }
  if(*right_part<height){
    *right_part+=1;
    printf("%d  ",node->data);
   
  }
  //Recursive call
  right_top(node->right,right_part,height+1);
  right_top(node->left,right_part,height-1);
 
}
int main(){

  struct Node*root=NULL;
  int left=-1,right=0;


  /*  Make A Binary Tree
  -----------------------
             1
           /   \
          2     3
         /     / \
        4     5   6
       /       \    
      7         8    
                 \
                  9
                   \
                    10
  */

  //Insertion of binary tree nodes
  root                    =insert(1);
  root->left              =insert(2);
  root->right             =insert(3);
  root->right->right      =insert(6);
  root->right->left       =insert(5);
  root->left->left        =insert(4);
  root->left->left->left  =insert(7);
  root->right->left->right =insert(8);
  root->right->left->right->right =insert(9);
  root->right->left->right->right->right =insert(10);

  //Display Left view of tree
  left_top(root,&left,0);
  //Display Right view of tree
  right_top(root,&right,0);


  return 0;
}

Output

1  2  4  7  3  6  10  
/*
   C++ Program 
   Print Top View of Binary Tree Using Recursion
*/
#include<iostream>
using namespace std;

//ure of Binary Tree node
class Node{
public:
  int data;
  Node*left,*right;
  //make a tree node
  Node(int data){
    //assign field values
    this->data=data;
    left=right=NULL;
  }
};


class BinaryTree{
public:
  Node*root;
  BinaryTree();
  void left_top(Node*,int* ,int);
  void right_top(Node*,int* ,int);
};

//set initial tree root to NULL
BinaryTree:: BinaryTree(){
  root=NULL;
}

//Print tree node in left view 
void  BinaryTree::left_top(Node*node,int *left_part,int height){

  if(node==NULL){
    return;
  }

  if(*left_part<height){
    //Get printed node
    *left_part+=1;
    //That is left view node
   cout<<"  "<<node->data;
  }
  //Recursive call
  left_top(node->left,left_part,height+1);
  left_top(node->right,left_part,height-1);

}

//Print right view nodes of tree from top to bottom elements
void  BinaryTree:: right_top( Node*node,int *right_part,int height){

  if(node==NULL){
    return;
  }
 
  if(*right_part<height){
    *right_part+=1;
     cout<<"  "<<node->data;
  }
  //Recursive call
  right_top(node->right,right_part,height+1);
  right_top(node->left,right_part,height-1);
 
}
int main(){
  //Make tree objects
  BinaryTree obj;
  int left=-1,right=0;


  /*  Make A Binary Tree
  -----------------------
             1
           /   \
          2     3
         /     / \
        4     5   6
       /       \    
      7         8    
                 \
                  9
                   \
                    10
  */

  //insert of binary tree nodes
  obj.root                    =new Node(1);
  obj.root->left              =new Node(2);
  obj.root->right             =new Node(3);
  obj.root->right->right      =new Node(6);
  obj.root->right->left       =new Node(5);
  obj.root->left->left        =new Node(4);
  obj.root->left->left->left  =new Node(7);
  obj.root->right->left->right =new Node(8);
  obj.root->right->left->right->right =new Node(9);
  obj.root->right->left->right->right->right =new Node(10);

  //Display Left view of tree
  obj.left_top(obj.root,&left,0);
  //Display Right view of tree
  obj.right_top(obj.root,&right,0);

  return 0;
}

Output

 1  2  4  7  3  6  10
/*  
   Java Program 
+  Print Top View of Binary Tree Using Recursion
 */


//Structure of Binary Tree node
class Node{
  public int data;
  public  Node left, right;
  //make a tree node
  public Node(int data){
        //assign field values
    this.data=data;
    left=right=null;
  }
}

class BinaryTree{

  public Node root;
  public int left,right;
  public BinaryTree(){
    //set initial tree root
    root=null;
    left=-1;
    right=0;
  }
    //Print tree node in left view 
  public void  leftTop(Node node,int height){

    if(node==null){
      return;
    }

    if(left<height){
      //Get printed node
      left+=1;
      //That is left view node
     System.out.print("  "+node.data);
    }
    //Recursive call
    leftTop(node.left,height+1);
    leftTop(node.right,height-1);

  }

  //Print right view nodes of tree from top to bottom elements
  void  rightTop( Node node,int height){

    if(node==null){
      return;
    }
   
    if(right<height){
      right+=1;
      System.out.print("  "+node.data);
    }
    //Recursive call
    rightTop(node.right,height+1);
    rightTop(node.left,height-1);
   
  }

  public static void main(String[] arges){
  BinaryTree obj=new BinaryTree();
  


  /*   Make A Binary Tree
  -----------------------
           1
         /   \
        2     3
       /     / \
      4     5   6
     /       \    
    7         8    
               \
                9
                 \
                  10
  */

  //insert of binary tree nodes
  obj.root                 =new Node(1);
  obj.root.left            =new Node(2);
  obj.root.right           =new Node(3);
  obj.root.right.right     =new Node(6);
  obj.root.right.left      =new Node(5);
  obj.root.left.left       =new Node(4);
  obj.root.left.left.left  =new Node(7);
  obj.root.right.left.right =new Node(8);
  obj.root.right.left.right.right =new Node(9);
  obj.root.right.left.right.right.right =new Node(10);

  //Display Left view of tree
  obj.leftTop(obj.root,0);
  //Display Right view of tree
  obj.rightTop(obj.root,0);
    }
  }

Output

  1  2  4  7  3  6  10
#Python Program 
#Print Top View of Binary Tree Using Recursion

      
class Node:
    def __init__(self,data):
      #Assign node value
      self.data=data
      self.left,self.right=None,None

class BinaryTree:

    def __init__(self):
      #set initial tree pointer to None
      self.root=None
      self.left=-1
      self.right=0

    def leftTop(self,node,height):

      if(node==None):
        return
      if(self.left<height):
        #Get printed node
        self.left+=1
        #That is left view node
        print(node.data,end="  ")
      #Recursive call
      self.leftTop(node.left,height+1)
      self.leftTop(node.right,height-1)

    

    #Print right view nodes of tree from top to bottom elements
    def rightTop(self,node,height):

      if(node==None):
        return
      
      if(self.right<height):
        self.right+=1
        print(node.data,end="  ")
      
      #Recursive call
      self.rightTop(node.right,height+1)
      self.rightTop(node.left,height-1)
     
    

def main():
  #Make object of Binary Tree
  obj=BinaryTree()
  #  Make A Binary Tree
  #-----------------------
  #          1
  #         /   \
  #        2     3
  #       /     / \
  #      4     5   6
  #     /       \    
  #    7         8    
  #               \
  #                9
  #                 \
  #                  10
  #/

  #insert of binary tree nodes
  obj.root=Node(1)
  obj.root.left=Node(2)
  obj.root.right=Node(3)
  obj.root.right.right=Node(6)
  obj.root.right.left=Node(5)
  obj.root.left.left=Node(4)
  obj.root.left.left.left=Node(7)
  obj.root.right.left.right=Node(8)
  obj.root.right.left.right.right =Node(9)
  obj.root.right.left.right.right.right =Node(10)

  #Display Left view of tree
  obj.leftTop(obj.root,0)
  #Display Right view of tree
  obj.rightTop(obj.root,0)

  

if __name__=="__main__":
  main()

Output

1  2  4  7  3  6  10
/*  
   C# Program 
+  Print Top View of Binary Tree Using Recursion
 */
using System;

//Structure of Binary Tree node
class Node{
  public int data;
  public  Node left, right;
  //make a tree node
  public Node(int data){
    //assign field values
    this.data=data;
    left=right=null;
  }
}

class BinaryTree{

  public Node root;
  public int left,right;
  public BinaryTree(){
    //set initial tree root
    root=null;
    left=-1;
    right=0;
  }
  //Print tree node in left view 
  public void  leftTop(Node node,int height){

    if(node==null){
      return;
    }

    if(left<height){
      //Get printed node
      left+=1;
      //That is left view node
      Console.Write(" {0}",node.data);
    }
    //Recursive call
    leftTop(node.left,height+1);
    leftTop(node.right,height-1);

  }

  //Print right view nodes of tree from top to bottom elements
  void  rightTop( Node node,int height){

    if(node==null){
      return;
    }

    if(right<height){
      right+=1;
      Console.Write(" {0}",node.data);
    }
    //Recursive call
    rightTop(node.right,height+1);
    rightTop(node.left,height-1);

  }

  public static void Main(String[] arges){
    BinaryTree obj=new BinaryTree();



    /*   Make A Binary Tree
  -----------------------
           1
         /   \
        2     3
       /     / \
      4     5   6
     /       \    
    7         8    
               \
                9
                 \
                  10
  */

    //insert of binary tree nodes
    obj.root                 =new Node(1);
    obj.root.left            =new Node(2);
    obj.root.right           =new Node(3);
    obj.root.right.right     =new Node(6);
    obj.root.right.left      =new Node(5);
    obj.root.left.left       =new Node(4);
    obj.root.left.left.left  =new Node(7);
    obj.root.right.left.right =new Node(8);
    obj.root.right.left.right.right =new Node(9);
    obj.root.right.left.right.right.right =new Node(10);

    //Display Left view of tree
    obj.leftTop(obj.root,0);
    //Display Right view of tree
    obj.rightTop(obj.root,0);
  }
}

Output

 1 2 4 7 3 6 10


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved