Ticker

20/recent/ticker-posts

Advertisement

Top View of Binary Tree

 Top View of Binary Tree

Top view of the binary tree results in nodes that are visible from the top of the tree.

Binary Tree

A binary tree is a non-linear data structure in which every node has at a most maximum of two children. So, in terms of binary tree construction, we should have a node with three-pointers one to hold data and two for left and right nodes.


In a binary search tree, the values are inserted based upon the properties left node contains values that are less than the root node and the right node contains values greater than the root node.

Binary Search Tree


class Bst {

    public class Node {
        int data;
        Node right;
        Node left;
        int height;

        Node(int dataint height) {
            this.height = height;
            this.data = data;
            left = right = null;
        }
    }



The above program has a constructor node for inserting data, on every insertion, it assigns the node with data and left, right as null with height zero. If the value is less than the root node it assigns the value to the left of the root and height is reduced by 1 and for the right, the height is increased by 1.

 public static Node root;

    public void insert(int data) {
        root = insertRecusrive(rootdata0);

    }

    public Bst.Node insertRecusrive(Node rootint dataint height) {
        if (root == null) {
            root = new Bst().new Node(dataheight);
            return root;

        } else if (data < root.data) {

            root.left = insertRecusrive(root.leftdataroot.height - 1);
        } else if (data > root.data) {
            root.right = insertRecusrive(root.rightdataroot.height + 1);
        }
        return root;
    }

Algorithm:

  • In every insertion check if the value is greater than the node or less than the node.
  • If it is less than the value of the root node then make a recursive call till the root is null on the left side and assign it with value and in every recursive call, the height is reduced by -1.
  • If it is greater than the value of the root node then make a recursive call till the root is null on the right side and assign it with value and in every recursive call, the height is increased by 1.
  • Create a map to hold the unique height values of node 
  • Traverse through the tree and check the value is in the map or not if it's unique print the value and add it to the map.
 Map<Integer, Integer> m = new LinkedHashMap<>();

    public void traversal(Node root) {

        if (!m.containsKey(root.height)) {
            m.put(root.heightroot.data);
            System.out.print(root.data + " ");

        }
        if (root.left != null) {
            traversal(root.left);

        }
        if (root.right != null) {
            traversal(root.right);

        }
  
The top view of the tree is: 4 2 1 5
As 1 and 3 are on the same level from the top view 3 is not visible hence it is skipped.


I hope you guys liked this article, here are some other articles you may like:

Post a Comment

0 Comments