Tuesday, April 13, 2021
More

    Binary Tree All In One

    Must Read

    Programmerhttp://www.improgrammer.net
    We started this site to inspire young minds to motivate and encourage them towards Programming Language. In this site you will get programming tutorials, tech, programming facts, programming fun and programming blogs.

    A binary tree is either empty or consists of a node called the root together with two binary trees called the left subtree and the right subtree.

            root
         /       \
      left      right
     /    \      /  \

    Some Facts:

    • If h = height of a binary tree,
    • max # of leaves = 2h
    • max # of nodes = 2h + 1 – 1
    • Total number of binary trees having n nodes
      • = number of stack-realizable permutations of length n
      • = number of well-formed parentheses (with n left parentheses and n right parentheses)
      • =(1/n+1)(2n C n) [Catalan Number]A binary tree with height h and 2h + 1 – 1 nodes (or 2h leaves) is called a full binary tree
    • A binary tree with n nodes is said to be complete if it contains all the first n nodes of the following numbering scheme
          1
      /      \
      2      3
      / \     /
      4  5  6
    • .Following is not complete binary tree
         4
      /   \
      2     7
      / \     \
      1   3     9
    • In a (balanced) binary tree with m nodes, moving from one level to the next requires one comparison, and there are log_2(m) levels, for a total of log_2(m) comparisons.
    • In contrast, an n-ary tree will require log_2(n) comparisons (using a binary search) to move to the next level. Since there are log_n(m) total levels, the search will require log_2(n)*log_n(m) = log_2(m) comparisons total. So, though n-ary trees are more complex, they provide no advantage in terms of total comparisons necessary.
    • The reason that binary trees are used more often than n-ary trees for searching is that n-ary trees are more complex, but usually provide no real speed advantage.

    Binary Tree Traversal:

    1. Preorder

    Visit root, visit left subtree in preorder, visit right subtree in preorder

    2. Postorder

    Visit left subtree in postorder, right subtree in postorder, then the root

    3. Inorder
    Visit left subtree in inorder, then the root, then the right subtree in inorder
    Example 1:
         1
      /    \
    2       3
    Pre: 123 (root, left, right)
    In : 213 (left, root, right)
    Post : 231 (left, right, root)
    Example 2 :
    1
      \
       2
          \
            3
    Pre: 123 (root, left, right)
    In : 123 (left, root, right)
    Post : 321 (left, right, root)

    Programming perspective

    A binary tree is a structure comprising nodes, where each node has the following 3 components:

    1. Data element: Stores any kind of data in the node
    2. Left pointer: Points to the tree on the left side of node
    3. Right pointer: Points to the tree on the right side of the node

    As the name suggests, the data element stores any kind of data in the node.
    The left and right pointers point to binary trees on the left and right side of the node respectively.

    If a tree is empty, it is represented by a null pointer.

    Commonly-used terminologies

    • Root: Top node in a tree
    • Child: Nodes that are next to each other and connected downwards
    • Parent: Converse notion of child
    • Siblings: Nodes with the same parent
    • Descendant: Node reachable by repeated proceeding from parent to child
    • Ancestor: Node reachable by repeated proceeding from child to parent.
    • Leaf: Node with no children
    • Internal node: Node with at least one child
    • External node: Node with no children

    Binary Tree Java Implementation :

    /*
     *  Binary Tree Java Implementation
     *  Includes tree traversal. (Preorder, Postorder, Inorder)
     */
     
     import java.util.Scanner;
     
     /* Class BTNode */
     class BTNode
     {    
         BTNode left, right;
         int data;
     
         /* Constructor */
         public BTNode()
         {
             left = null;
             right = null;
             data = 0;
         }
         /* Constructor */
         public BTNode(int n)
         {
             left = null;
             right = null;
             data = n;
         }
         /* Function to set left node */
         public void setLeft(BTNode n)
         {
             left = n;
         }
         /* Function to set right node */ 
         public void setRight(BTNode n)
         {
             right = n;
         }
         /* Function to get left node */
         public BTNode getLeft()
         {
             return left;
         }
         /* Function to get right node */
         public BTNode getRight()
         {
             return right;
         }
         /* Function to set data to node */
         public void setData(int d)
         {
             data = d;
         }
         /* Function to get data from node */
         public int getData()
         {
             return data;
         }     
     }
     
     /* Class BT */
     class BT
     {
         private BTNode root;
     
         /* Constructor */
         public BT()
         {
             root = null;
         }
         /* Function to check if tree is empty */
         public boolean isEmpty()
         {
             return root == null;
         }
         /* Functions to insert data */
         public void insert(int data)
         {
             root = insert(root, data);
         }
         /* Function to insert data recursively */
         private BTNode insert(BTNode node, int data)
         {
             if (node == null)
                 node = new BTNode(data);
             else
             {
                 if (node.getRight() == null)
                     node.right = insert(node.right, data);
                 else
                     node.left = insert(node.left, data);             
             }
             return node;
         }     
         /* Function to count number of nodes */
         public int countNodes()
         {
             return countNodes(root);
         }
         /* Function to count number of nodes recursively */
         private int countNodes(BTNode r)
         {
             if (r == null)
                 return 0;
             else
             {
                 int l = 1;
                 l += countNodes(r.getLeft());
                 l += countNodes(r.getRight());
                 return l;
             }
         }
         /* Function to search for an element */
         public boolean search(int val)
         {
             return search(root, val);
         }
         /* Function to search for an element recursively */
         private boolean search(BTNode r, int val)
         {
             if (r.getData() == val)
                 return true;
             if (r.getLeft() != null)
                 if (search(r.getLeft(), val))
                     return true;
             if (r.getRight() != null)
                 if (search(r.getRight(), val))
                     return true;
             return false;         
         }
         /* Function for inorder traversal */
         public void inorder()
         {
             inorder(root);
         }
         private void inorder(BTNode r)
         {
             if (r != null)
             {
                 inorder(r.getLeft());
                 System.out.print(r.getData() +" ");
                 inorder(r.getRight());
             }
         }
         /* Function for preorder traversal */
         public void preorder()
         {
             preorder(root);
         }
         private void preorder(BTNode r)
         {
             if (r != null)
             {
                 System.out.print(r.getData() +" ");
                 preorder(r.getLeft());             
                 preorder(r.getRight());
             }
         }
         /* Function for postorder traversal */
         public void postorder()
         {
             postorder(root);
         }
         private void postorder(BTNode r)
         {
             if (r != null)
             {
                 postorder(r.getLeft());             
                 postorder(r.getRight());
                 System.out.print(r.getData() +" ");
             }
         }     
     }
     
     /* Class BinaryTree */
     public class BinaryTree
     {
         public static void main(String[] args)
        {            
            Scanner scan = new Scanner(System.in);
            /* Creating object of BT */
            BT bt = new BT(); 
            /*  Perform tree operations  */
            System.out.println("Binary Tree Test\n");          
            char ch;        
            do    
            {
                System.out.println("\nBinary Tree Operations\n");
                System.out.println("1. insert ");
                System.out.println("2. search");
                System.out.println("3. count nodes");
                System.out.println("4. check empty");
     
                int choice = scan.nextInt();            
                switch (choice)
                {
                case 1 : 
                    System.out.println("Enter integer element to insert");
                    bt.insert( scan.nextInt() );                     
                    break;                          
                case 2 : 
                    System.out.println("Enter integer element to search");
                    System.out.println("Search result : "+ bt.search( scan.nextInt() ));
                    break;                                          
                case 3 : 
                    System.out.println("Nodes = "+ bt.countNodes());
                    break;     
                case 4 : 
                    System.out.println("Empty status = "+ bt.isEmpty());
                    break;            
                default : 
                    System.out.println("Wrong Entry \n ");
                    break;   
                }
                /*  Display tree  */ 
                System.out.print("\nPost order : ");
                bt.postorder();
                System.out.print("\nPre order : ");
                bt.preorder();
                System.out.print("\nIn order : ");
                bt.inorder();
     
                System.out.println("\n\nDo you want to continue (Type y or n) \n");
                ch = scan.next().charAt(0);                        
            } while (ch == 'Y'|| ch == 'y');               
        }
     }

    Applications of binary trees

    • Binary Search Tree – Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages’ libraries. These are a data structure in which searching, insertion, and removal are all very fast (about log(n) operations).
    • Binary Space Partition – Used in almost every 3D video game to determine what objects need to be rendered.
    • Binary Tries – Used in almost every high-bandwidth router for storing router-tables.
    • Hash Trees – used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available.
    • Heaps – Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort.
    • Huffman Coding Tree – used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats.
    • GGM Trees – Used in cryptographic applications to generate a tree of pseudo-random numbers.
    • Syntax Tree – Constructed by compilers and (implicitly) calculators to parse expressions.
    • Treap – Randomized data structure used in wireless networking and memory allocation.
    • T-tree – Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.
    • a Manipulate hierarchical data
    • Make information easy to search (see tree traversal)
    • Manipulate sorted lists of data
    • Use as a workflow for compositing digital images for visual effects
    • Use in router algorithms

     

    Comment or email us [email protected] if you have any questions related to binary tree.

    Latest Articles

    More Recipes Like This