draw an object model for a binary tree

Overview

A binary tree is a tree-type non-linear data structure with a maximum of two children for each parent. Every node in a binary tree has a left and right reference along with the data element. The node at the top of the hierarchy of a tree is called the root node.

Scope

• This article tells about the working of the Binary tree.
• Terminologies in Binary tree
• Different types of binary tree
• Binary tree in different programming languages.
• Time complexity analysis of Binary tree.

Takeaways

A binary tree is the specialized version of the General tree. A binary tree is a tree in which each node can have at most two nodes.

Complexity of Binary Tree

• Time complexity - O( $n$ )
• Space complexity - O( $n$ )

What are Binary Trees?

Imagine that your college is going to organize a fest, and you are given the responsibility of managing the entire event. Would you do all the work on your own or are you likely to divide the entire team into smaller parts and assign a task to each one of them? In this case, the second option seems to be a better one. You can divide the team into smaller teams like sponsorship, technical, etc., and each team can have a leader who would instruct the other members of the team.

Notice that doing this would create a hierarchical structure where you are the person at the top, then at the second level you have team leaders, and at the third level, each team has some volunteers. This is what trees are! There is only one element at the top, and each element has some children and grandchildren.

A binary tree is a tree data structure(we shall add a link to the tree article here) whose all nodes have either zero, one, or at most two children nodes. These two children are generally referred to as left and right child respectively.

The top-most node is known as the root node, while the nodes with no children are known as leaf nodes.

Notice how the nodes A, B & C contain at most two child nodes. Therefore, the above-given diagram represents a binary tree.

Each node in a binary tree has these three elements –

1. Data item that is the data stored in the node
2. Address of the left child
3. Address of the right child

   

Terminologies in Binary Trees

1. Nodes – Nodes are the building blocks of any data structure. They majorly contain some data and link to the next/previous nodes. In the case of binary trees, they contain the address of the left and the right child respectively.

2. Root – The topmost node in a tree is known as the root node. A tree can have at most one root node.

3. Parent Node – A node (except the root) that has a succeeding node is known as a parent node.

4. Child Node – A node that has a preceding node is known as a child node. A node can be both parent and child depending on the node that is in context.

5. Leaf Node – A node with no children.

6. Internal Node – A node that has at least one child node is known as an internal node.

7. Depth of a Binary Tree – The number of edges from a node in the tree to the root node.

8. Height of a Binary Tree – The number of edges from the deepest node in the tree to the root node.

The following diagram illustrates all the terminologies in a binary tree –

Now let's discuss some of the properties of a binary tree

Properties of Binary Trees

1. If there are n nodes in a perfect binary tree (we would read more about them), its height is given by – $log n$ . This is because, for a given node in a binary tree, there can be at most 2 child nodes. This further drives us to the explanation that at each level or height of a binary tree, the number of nodes will be almost equal to half of the number of nodes present in the next level. To put it simply, in a binary tree, the number of nodes at each level is almost double the number of nodes at the previous level.

---

It means, for a binary tree with the height h, Total number of nodes, n = $(2 ^ 0) + (2 ^ 1) + (2 ^ 2) + (2 ^ 3) + ….. + (2 ^ (h-1))$

From `mathematical induction, we also know that

$(2 ^ 0) + (2 ^ 1) + (2 ^ 2) + (2 ^ 3) + ….. + (2 ^ {(h-1)}) = (2 ^ h)-1$

Therefore,

$(2 ^ h)-1 = n => 2 ^ h = n + 1 => h = log2(n+1)$

Therefore, the minimum height of a binary tree is almost equal to log(n).

---

2. The minimum number of nodes possible at the height h of a binary tree is given by h+1.

3. If a binary tree has L number of leaf nodes, its height is given by L + 1

4. At each level i of a binary tree, the number of total nodes is given by 2 ^ i.

Types of Binary Trees

Binary Trees are of many types, and each of these trees has its own properties and characteristics.

Let's discuss some of them in detail –

1. Full Binary Tree

A full binary tree, also known as a proper binary tree, is a tree in which each internal node has either zero or two children nodes is known as a full binary tree.

In other words, if in a binary tree a node contains only one child node, it is not a full binary tree.

The following diagrams shows a full binary tree –

Notice how each node has either zero or two children nodes.

In a full binary tree, if there are n number of total nodes –

• The number of internal nodes is given by (n-1)/2
• The number of leaf nodes is given by (n+1)/2

2. Complete Binary Tree

A complete binary tree is a binary tree in which all the elements are arranged without missing any sequence.

In a complete binary tree –

• All the levels are completely filled except the last level that may or may not be completely filled.
• Elements are filled from left to right.

The following trees are complete binary trees since they have no empty spaces in them.

3. Perfect Binary Trees

If in a tree all the internal nodes have exactly two children nodes, it is known as a perfect binary tree.

In a perfect binary tree, all the leaf nodes are on the same level.

The following diagrams represents a perfect binary tree –

Consider a perfect binary tree with height h, the total number of nodes in this case is given by 2h – 1.

4. Degenerate Binary Trees

If in a binary tree each node contains only one child node either on the left side or the right side of the tree, it is known as a degenerate binary tree.

Degenerate binary trees are equal to linked lists in terms of performance. The following tree shows a degenerate binary tree –

Degenerate binary trees can also be classified into two types –

a. Left-skewed – A degenerate binary tree in which all the nodes lean towards the left side of the tree. The following diagram shows a left-skewed degenerate binary tree –

b. Right-skewed – A degenerate binary tree in which all the nodes lean towards the right side of the tree. The following diagram shows a right-skewed degenerate binary tree –

5. Balanced Binary Trees

A binary tree is said to be balanced if the height of the left and the right subtrees differ by 0 or 1.

In a balanced binary tree, both the left and right trees are also balanced. The following diagram shows a balanced binary tree –

Notice that in the first image, the right subtree is at the height of 3, and the left subtree is at 2. The difference between the heights of the left and the right subtree is therefore 1. Therefore, the given tree is a balanced binary tree.

In the second image, the right subtree is at the height of 3, whereas the left subtree is at 1. The difference between the heights of the left and the right subtrees is 2. It violates the condition of a balanced binary tree. Hence, the given tree is not a balanced binary tree.

Now that we know what binary trees are, let's write some code to implement them.

Implementation of Binary Trees

1. Binary Tree Program in C

            
              
                                  //structure that contains data, address of the left child, and the address of the right child                                                                        struct                                                      node                                      {                                                                                          int                                      item;                                                                        struct                                                      node                  *                                    left                  ;                                                                                          struct                                                      node                  *                                    right                  ;                                    };                                                       // function to create a new node                                                                        struct node*                                    createNode                  (                  int                                      data)                                                      {                                                                        //allocating space for new node                                                                                          struct                                                      node                                      *                  node                                      =                                      (struct node *)                  malloc                  (                  sizeof                  (struct node));                                                                        //inserting data in the node                                                      node->item = data;                                                      //setting left and right child as NULL                                                                          node->left =                                    NULL                  ;                                                        node->right =                                    NULL                  ;                                                                        return                                      node;                  }                                                       // Insert to the left of the node                                                                        struct node*                                    insertLeft                  (struct node* root,                                    int                                      value)                                                      {                                    root->left = createNode(value);                                                      return                                      root->left;                  }                                                       // Inserting to the right of the node                                                                        struct node*                                    insertRight                  (struct node* root,                                    int                                      value)                                                      {                                    root->right = createNode(value);                                                      return                                      root->right;                  }                              
            
          

2. Binary Tree Program in C++

            
              
                                  // Binary Tree in C++                                                                        //structure that contains data, address of left child, address of the right child                                                                        struct                                                      Node                                      {                                                                                          int                                      data;                                                                        struct                                                      node                                      *                  left                  ;                                                                                          struct                                                      node                                      *                  right                  ;                                    };                                                       // function to create a new node                                                                        Node *                  newNode                  (                  int                                      data)                                                      {                                                                        //allocating space for the node                                                                          Node *node =                                    new                                      Node;                                                                        //storing in the data                                                      node->data = data;                                                      //setting left and right children to NULL                                                                          node->left =                                    NULL                  ;                                                        node->right =                                    NULL                  ;                                                                        return                                      (node);                  }                              
            
          

3. Binary Tree Program in Java

            
              
                                  // Binary Tree in Java                                                                        // creating a node that holds the data, address of the left child, and the address of the right child                                                                        class                                                      Node                                                      {                                                                        int                                      key;                                    Node left, right;                                                                         //setting data in the node                                                                                          public                                                      Node                  (                  int                                      item)                                                      {                                    key = item;                                                      //setting left and right child equal to NULL                                                                          left = right =                                    null                  ;                                    }                   }                                                       class                                                      BinaryTree                                                      {                                    Node root;                                                      //inserting data into the binary tree                                                                          BinaryTree(                  int                                      key) {                                                        root =                                    new                                      Node(key);                                    }                                                                         //set root NULL when the binary tree is created for the first time                                                      BinaryTree() {                                      root =                                    null                  ;                                    }                                                                         public                                                      static                                                      void                                                      main                  (String[] args)                                                      {                                                                        //creating a new instance of Binary Tree                                                                          BinaryTree tree =                                    new                                      BinaryTree();                                                                        //inserting into the binary tree                                                                          tree.root =                                    new                                      Node(                  1                  );                                                        tree.root.left =                                    new                                      Node(                  2                  );                                                        tree.root.right =                                    new                                      Node(                  3                  );                                    }                   }                              
            
          

4. Binary Tree Program in Python

            
              
                                  # Binary Tree in Python                                                                        # node that hold data, address of the left child, and address of the right child                                                                        class                                                      Node                  :                                                                                          def                                                      __init__                  (                  self, key                  ):                                                                                          # setting left and right child equal to NULL                                                                          self.left =                                    None                                                                          self.right =                                    None                                                                                          # inserting data into the node                                                      self.val = key                                     root = Node(                  1                  )                                    root.left = Node(                  2                  )                                    root.right = Node(                  3                  )                                                
            
          

Now let's discuss some benefits of binary trees.

Benefits of Binary Trees

1. Binary trees are used in binary search trees. It helps in searching for elements in a faster and efficient way.

2. Binary trees are also used in heaps that are special kind of binary trees. Heaps are used in heap sort, which is an efficient sorting algorithm. Heaps are also used in building priority queues in which elements are arranged in the order of their priorities.

3. Binary trees are used in converting different prefix and postfix expressions.

4. Binary trees are also used in graph traversal algorithms like Dijkastra's algorithm.

5. Some real-life applications of binary trees include virtual memory management, and 3D where faster rendering of objects is required.

Binary tree Time Complexity

Searching: Worst case complexity of O(n). Insertion: Worst case complexity of O(n). Deletion: Worst case complexity of O(n).

Binary tree Space Complexity

Searching: O(n). Insertion: O(n). Deletion: O(n).

Conclusion

• Binary trees are a very important data structure used extensively in programming.
• An ideal way to go with the hierarchical way of storing data.
• Reflect structural relationships that exist in the given data set.
• Make insertion and deletion faster than linked lists and arrays.
• A flexible way of holding and moving data.

garciaspeausell.blogspot.com

Source: https://www.scaler.com/topics/data-structures/binary-tree-in-data-structure/

Share this post