Print vertical Traversal of binary tree

Vertical traversal of binary tree

Here given code implementation process.

/*
  C Program 
+ Vertical view of binary tree
*/
#include<stdio.h>
#include<stdlib.h>
//structure of Binary Tree node
struct Node
{
  int data;
  struct Node*left,*right;
};

struct List
{
  int order,data;
  struct List*next;
  
};
//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;
  
}
//Adding a new element in sorted order when get new vertical element
void addList(struct List**result,int order,int data)
{
  struct List*new_node=NULL,*per=NULL;
 
  new_node=(struct List*)malloc(sizeof(struct List));
  new_node->next=NULL;
  new_node->data=data;
  new_node->order=order;
  if(*result!=NULL)
  {
    struct List*temp=*result;
    if(temp->order>order)
    {
      //smallest element
      new_node->next= *result;
      *result=new_node;
    }else{

      while(temp!=NULL && temp->order < order)
      {
        per=temp;
        temp=temp->next;
      }
      new_node->next=per->next;
      per->next=new_node;
      
    }

  }else{
    //When first element of list
    *result=new_node;
  }
}
void removeList(struct List**bucket)
{
  struct List*temp=NULL;
  while(*bucket)
  {
    temp=*bucket;
    *bucket=temp->next;
    free(temp);
    temp=NULL;
  }
}

void get_vertical(struct Node*node,struct List**bucket,int order)
{

  if(node!=NULL){
    
    get_vertical(node->left,bucket,order-1);
   
    get_vertical(node->right,bucket,order+1);
    addList(bucket,order,node->data);
  }
}
void vertical_view(struct List*bucket)
{
  struct List*temp=bucket;
  while(temp!=NULL)
  {
    printf("%3d",temp->data );
    temp=temp->next;
  }

}
int main(){

  struct Node*root=NULL;
  struct List*bucket=NULL;

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

  */
  //Insertion of binary tree nodes

  root               = insert(10);
  root->left         = insert(2);
  root->left->left   = insert(3);
  root->left->left->right = insert(9);
  root->right        = insert(4);
  root->right->right = insert(5);
  root->right->left  = insert(6);

  root->right->left->right  = insert(7);
  root->right->left->right->right  = insert(11);
  root->left->left->right->right   = insert(1);

  get_vertical(root,&bucket,0);
  vertical_view(bucket);
  removeList(&bucket);

  return 0;
}

Output

3  2  9 10  6  1  4  7  5 11
/*
  C++ Program
  Vertical Traversal of binary tree
*/
#include <iostream>

using namespace std;


class Node {

  public:
    int data;

  Node *left, *right;

  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};

class List {

  public:
    int order, data;
  List *next;
  List(int value, int level) {
    this->data = value;
    this->order = level;
    this->next = NULL;
  }
};
class BinaryTree {
  public:
    Node *root;
  List *result;
  BinaryTree() {
    root = NULL;
    result = NULL;
  }
  void addList(int level, int value) {
    List *new_node = NULL, *per = NULL;
    new_node = new List(value, level);


    if (result != NULL) {

      List *temp = result;

      if (temp->order > level) {
        new_node->next = result;
        result = new_node;
      } else {

        while (temp != NULL && temp->order < level) {
          per = temp;
          temp = temp->next;
        }
        new_node->next = per->next;
        per->next = new_node;
      }
    } else {
      result = new_node;
    }
  }
  void removeList() {
    List *temp = NULL;

    while (result != NULL) {
      temp = result;
      result = temp->next;
      delete temp;
      temp = NULL;
    }
  }
  void get_vertical(Node *node, int level) {

    if (node != NULL) {
      get_vertical(node->left, level - 1);
      get_vertical(node->right, level + 1);
      addList(level, node->data);
    }
  }
  void vertical_view() {
    List *temp = result;

    while (temp != NULL) {
      cout << "  " << temp->data;
      temp = temp->next;
    }
  }
};
int main() {

  BinaryTree obj = BinaryTree();

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

  */
  obj.root = new Node(10);
  obj.root->left = new Node(2);
  obj.root->left->left = new Node(3);
  obj.root->left->left->right = new Node(9);
  obj.root->right = new Node(4);
  obj.root->right->right = new Node(5);
  obj.root->right->left = new Node(6);
  obj.root->right->left->right = new Node(7);
  obj.root->right->left->right->right = new Node(11);
  obj.root->left->left->right->right = new Node(1);
  obj.get_vertical(obj.root, 0);
  obj.vertical_view();
  obj.removeList();
  return 0;
}

Output

3  2  9  10  6  1  4  7  5  11
/*
  Java Program
  Vertical Traversal of binary tree
*/
class Node {

  public int data;

  public Node left, right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}

class List {

  public int order, data;

  public List next;
  public List(int value, int level) {
    data = value;
    order = level;
    next = null;
  }
}
class BinaryTree {
  public Node root;
  public List result;
  public BinaryTree() {
    root = null;
    result = null;
  }
  public void addList(int level, int data) {
    List new_node = null, per = null;
    new_node = new List(data, level);


    if (result != null) {

      List temp = result;

      if (temp.order > level) {
        new_node.next = result;
        result = new_node;
      } else {

        while (temp != null && temp.order < level) {
          per = temp;
          temp = temp.next;
        }
        new_node.next = per.next;
        per.next = new_node;
      }
    } else {
      result = new_node;
    }
  }
  public void removeList() {
    List temp = null;

    while (result != null) {
      temp = result;
      result = temp.next;
      temp = null;
    }
  }
  public void get_vertical(Node node, int order) {

    if (node != null) {
      get_vertical(node.left, order - 1);
      get_vertical(node.right, order + 1);
      addList(order, node.data);
    }
  }
  public void vertical_view() {
    List temp = result;

    while (temp != null) {
      System.out.printf("%3d", temp.data);
      temp = temp.next;
    }
  }
  public static void main(String[] args) {

    BinaryTree obj = new BinaryTree();

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

    */
    obj.root = new Node(10);
    obj.root.left = new Node(2);
    obj.root.left.left = new Node(3);
    obj.root.left.left.right = new Node(9);
    obj.root.right = new Node(4);
    obj.root.right.right = new Node(5);
    obj.root.right.left = new Node(6);
    obj.root.right.left.right = new Node(7);
    obj.root.right.left.right.right = new Node(11);
    obj.root.left.left.right.right = new Node(1);
    obj.get_vertical(obj.root, 0);
    obj.vertical_view();
    obj.removeList();

  }
}

Output

 3  2  9 10  6  1  4  7  5 11
class Node :

  def __init__(self,value) :
    self.data = value;
    self.left = None;
    self.right = None;
  

class List :

  def __init__(self,value, level) :
    self.data = value;
    self.order = level;
    self.next = None;
  

class BinaryTree :

  def __init__(self) :
    self.root = None;
    self.result = None;
  
  def addList(self,level, value) :
    new_node = None;
    per = None;
    new_node = List(value, level);
    if (self.result != None) :
      temp = self.result;
      if (temp.order > level) :
        new_node.next = self.result;
        self.result = new_node;
      else :
        while (temp != None and temp.order < level) :
          per = temp;
          temp = temp.next;
        
        new_node.next = per.next;
        per.next = new_node;
      
    else :
      self.result = new_node;
    
  
  
  def get_vertical(self,node, level) :
    if (node != None) :
      self.get_vertical(node.left, level - 1);
      self.get_vertical(node.right, level + 1);
      self.addList(level, node.data);
    
  
  def vertical_view(self) :
    temp = self.result;
    while (temp != None) :
      print(temp.data,end=" ");
      temp = temp.next;
    
  
def main() :
  obj = BinaryTree();
  #  Make A Binary Tree
  #          10
  #         /  \
  #        2    4
  #       /    / \
  #      3    6   5
  #       \    \
  #        9    7
  #         \    \
  #          1    11
  #   
  obj.root = Node(10);
  obj.root.left = Node(2);
  obj.root.left.left = Node(3);
  obj.root.left.left.right = Node(9);
  obj.root.right = Node(4);
  obj.root.right.right = Node(5);
  obj.root.right.left = Node(6);
  obj.root.right.left.right = Node(7);
  obj.root.right.left.right.right = Node(11);
  obj.root.left.left.right.right = Node(1);
  obj.get_vertical(obj.root, 0);
  obj.vertical_view();
  

if __name__ == "__main__":
  main()

Output

3 2 9 10 6 1 4 7 5 11 
/*
  C# Program
  Vertical Traversal of binary tree
*/
using System;
class Node {

  public int data;

  public Node left, right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}

class List {

  public int order, data;

  public List next;
  public List(int value, int level) {
    data = value;
    order = level;
    next = null;
  }
}
class BinaryTree {
  public Node root;
  public List result;
  public BinaryTree() {
    root = null;
    result = null;
  }
  public void addList(int level, int value) {
    List new_node = null, per = null;
    new_node = new List(value, level);


    if (result != null) {

      List temp = result;

      if (temp.order > level) {
        new_node.next = result;
        result = new_node;
      } else {

        while (temp != null && temp.order < level) {
          per = temp;
          temp = temp.next;
        }
        new_node.next = per.next;
        per.next = new_node;
      }
    } else {
      result = new_node;
    }
  }
  public void removeList() {
    List temp = null;

    while (result != null) {
      temp = result;
      result = temp.next;
      temp = null;
    }
  }
  public void get_vertical(Node node, int level) {

    if (node != null) {
      get_vertical(node.left, level - 1);
      get_vertical(node.right, level + 1);
      addList(level, node.data);
    }
  }
  public void vertical_view() {
    List temp = result;

    while (temp != null) {
      Console.Write("  {0}", temp.data);
      temp = temp.next;
    }
  }
  public static void Main(String[] args) {

    BinaryTree obj = new BinaryTree();

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

        */
    obj.root = new Node(10);
    obj.root.left = new Node(2);
    obj.root.left.left = new Node(3);
    obj.root.left.left.right = new Node(9);
    obj.root.right = new Node(4);
    obj.root.right.right = new Node(5);
    obj.root.right.left = new Node(6);
    obj.root.right.left.right = new Node(7);
    obj.root.right.left.right.right = new Node(11);
    obj.root.left.left.right.right = new Node(1);
    obj.get_vertical(obj.root, 0);
    obj.vertical_view();
    obj.removeList();

  }
}

Output

  3  2  9  10  6  1  4  7  5  11
<?php
/*
  Php Program
  Vertical Traversal of binary tree
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class Record {
  public $order;
  public $data;
  public $next;

  function __construct($value, $level) {
    $this->data = $value;
    $this->order = $level;
    $this->next = null;
  }
}
class BinaryTree {
  public $root;
  public $result;

  function __construct() {
    $this->root = null;
    $this->result = null;
  }
  public  function addRecord($level, $value) {
    $new_node = null;
    $per = null;
    $new_node = new Record($value, $level);
    if ($this->result != null) {
      $temp = $this->result;
      if ($temp->order > $level) {
        $new_node->next = $this->result;
        $this->result = $new_node;
      } else {
        while ($temp != null && $temp->order < $level) {
          $per = $temp;
          $temp = $temp->next;
        }
        $new_node->next = $per->next;
        $per->next = $new_node;
      }
    } else {
      $this->result = $new_node;
    }
  }

  public  function get_vertical($node, $level) {
    if ($node != null) {
      $this->get_vertical($node->left, $level - 1);
      $this->get_vertical($node->right, $level + 1);
      $this->addRecord($level, $node->data);
    }
  }
  public  function vertical_view() {
    $temp = $this->result;
    while ($temp != null) {
      printf("%3d", $temp->data);
      $temp = $temp->next;
    }
  }
}
function main() {
  $obj = new BinaryTree();

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

  */
  $obj->root = new Node(10);
  $obj->root->left = new Node(2);
  $obj->root->left->left = new Node(3);
  $obj->root->left->left->right = new Node(9);
  $obj->root->right = new Node(4);
  $obj->root->right->right = new Node(5);
  $obj->root->right->left = new Node(6);
  $obj->root->right->left->right = new Node(7);
  $obj->root->right->left->right->right = new Node(11);
  $obj->root->left->left->right->right = new Node(1);
  $obj->get_vertical($obj->root, 0);
  $obj->vertical_view();

}
main();
?>

Output

 3  2  9 10  6  1  4  7  5 11
/*
  Node (JS) Program
  Vertical Traversal of binary tree
*/

class Node {

  constructor(value) {
    this.data = value;
    this.left = null;
    this.right = null;
  }
}
class List {

  constructor(value, level) {
    this.data = value;
    this.order = level;
    this.next = null;
  }
}
class BinaryTree {

  constructor() {
    this.root = null;
    this.result = null;
  }
  addList(level, value) {
    var new_node = null;
    var per = null;
    new_node = new List(value, level);
    if (this.result != null) {
      var temp = this.result;
      if (temp.order > level) {
        new_node.next = this.result;
        this.result = new_node;
      } else {
        while (temp != null && temp.order < level) {
          per = temp;
          temp = temp.next;
        }
        new_node.next = per.next;
        per.next = new_node;
      }
    } else {
      this.result = new_node;
    }
  }
  removeList() {
    var temp = null;
    while (this.result != null) {
      temp = this.result;
      this.result = temp.next;
      temp = null;
    }
  }
  get_vertical(node, level) {
    if (node != null) {
      this.get_vertical(node.left, level - 1);
      this.get_vertical(node.right, level + 1);
      this.addList(level, node.data);
    }
  }
  vertical_view() {
    var temp = this.result;
    while (temp != null) {
      process.stdout.write("  " + temp.data);
      temp = temp.next;
    }
  }
}

function main() {
  var obj = new BinaryTree();
  /* Make A Binary Tree
      ------------------
          10
         /  \
        2    4
       /    / \
      3    6   5
       \    \
        9    7
         \    \
          1    11 

   */
  obj.root = new Node(10);
  obj.root.left = new Node(2);
  obj.root.left.left = new Node(3);
  obj.root.left.left.right = new Node(9);
  obj.root.right = new Node(4);
  obj.root.right.right = new Node(5);
  obj.root.right.left = new Node(6);
  obj.root.right.left.right = new Node(7);
  obj.root.right.left.right.right = new Node(11);
  obj.root.left.left.right.right = new Node(1);
  obj.get_vertical(obj.root, 0);
  obj.vertical_view();
  obj.removeList();
}
main();

Output

 3  2  9  10  6  1  4  7  5  11
#Ruby Program
#Vertical Traversal of binary tree
class Node 
  attr_reader :data, :left, :right
  attr_accessor :data, :left, :right
  def initialize(value) 
    @data = value
    @left = nil
    @right = nil
  end
end

class List 
  attr_reader :order, :data, :next
  attr_accessor :order, :data, :next
  def initialize(value, level) 
    @data = value
    @order = level
    @next = nil
  end
end

class BinaryTree 
  attr_reader :root, :result
  attr_accessor :root, :result
  def initialize() 
    @root = nil
    @result = nil
  end
  def addList(level, value) 
    new_node = nil
    per = nil
    new_node = List.new(value, level)
    if (@result != nil) 
      temp = @result
      if (temp.order > level) 
        new_node.next = @result
        @result = new_node
      else 
        while (temp != nil and temp.order < level) 
          per = temp
          temp = temp.next
        end
        new_node.next = per.next
        per.next = new_node
      end
    else 
      @result = new_node
    end
  end
  def removeList() 
    temp = nil
    while (@result != nil) 
      temp = @result
      @result = temp.next
      temp = nil
    end
  end
  def get_vertical(node, level) 
    if (node != nil) 
      self.get_vertical(node.left, level - 1)
      self.get_vertical(node.right, level + 1)
      self.addList(level, node.data)
    end
  end
  def vertical_view() 
    temp = @result
    while (temp != nil) 
      print("  ", temp.data)
      temp = temp.next
    end
  end
end

def main() 
  obj = BinaryTree.new()
  #  Make A Binary Tree
  #          10
  #         /  \
  #        2    4
  #       /    / \
  #      3    6   5
  #       \    \
  #        9    7
  #         \    \
  #          1    11
  #   
  obj.root = Node.new(10)
  obj.root.left = Node.new(2)
  obj.root.left.left = Node.new(3)
  obj.root.left.left.right = Node.new(9)
  obj.root.right = Node.new(4)
  obj.root.right.right = Node.new(5)
  obj.root.right.left = Node.new(6)
  obj.root.right.left.right = Node.new(7)
  obj.root.right.left.right.right = Node.new(11)
  obj.root.left.left.right.right = Node.new(1)
  obj.get_vertical(obj.root, 0)
  obj.vertical_view()
  obj.removeList()
end
main()

Output

 3  2  9  10  6  1  4  7  5  11
/*
  Swift4 Program
  Vertical Traversal of binary tree
*/

class Node {
  var data : Int;
  var left : Node?;
  var right : Node?;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class List {
  var order : Int;
  var data : Int;
  var next : List?;
  init(_ value: Int, _ level: Int) {
    self.data = value;
    self.order = level;
    self.next = nil;
  }
}
class BinaryTree {
  var root : Node?;
  var result : List?;
  init() {
    self.root = nil;
    self.result = nil;
  }
  func addList(_ level: Int, _ value: Int) {
    var new_node: List? = nil;
    var per : List? = nil;
    new_node = List(value, level);
    if (self.result != nil) {
      var temp: List? ;
      temp = self.result;
      if (temp!.order > level) {
        new_node!.next = self.result;
        self.result = new_node;
      } else {
        while (temp != nil && temp!.order < level) {
          per = temp;
          temp = temp!.next;
        }
        new_node!.next = per!.next;
        per!.next = new_node;
      }
    }
    else {
      self.result = new_node;
    }
  }
  func removeList() {
    var temp: List? = nil;
    while (self.result != nil) {
      temp = self.result;
      self.result = temp!.next;
      temp = nil;
    }
  }
  func get_vertical(_ node: Node?, _ level: Int) {
    if (node != nil) {
      self.get_vertical(node!.left, level - 1);
      self.get_vertical(node!.right, level + 1);
      self.addList(level, node!.data);
    }
  }
  func vertical_view() {
    var temp : List? = self.result;
    while (temp != nil) {
      print("\(temp!.data)",terminator:" ");
  
      temp = temp!.next;
    }
  }
  
}
func main() {
    let obj : BinaryTree? = BinaryTree();
    /*  Make A Binary Tree
    -----------------------
          10
         /  \
        2    4
       /    / \
      3    6   5
       \    \
        9    7
         \    \
          1    11 

    */
    obj!.root = Node(10);
    obj!.root!.left = Node(2);
    obj!.root!.left!.left = Node(3);
    obj!.root!.left!.left!.right = Node(9);
    obj!.root!.right = Node(4);
    obj!.root!.right!.right = Node(5);
    obj!.root!.right!.left = Node(6);
    obj!.root!.right!.left!.right = Node(7);
    obj!.root!.right!.left!.right!.right = Node(11);
    obj!.root!.left!.left!.right!.right = Node(1);
    obj!.get_vertical(obj!.root, 0);
    obj!.vertical_view();
    obj!.removeList();
  }
main();

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