A Concise Overview of The Binary Trees

Your Compact Guide to Understanding The Fundamentals of Binary Tree Data Structure

Fig 1: “Within the branches lies the secrets of Infinite Realities”

In the world of data structures, few concepts are as elegant and powerful as the Tree Data Structure. Imagine a family tree where heirs and lineage stretch across time, branching out from the core of an ancient oak — a living chronicle.

Binary trees, where each node has at most two children, are more than abstract mathematical concepts — they power countless algorithms and solve complex computational problems in the area of operating systems, databases, networking and many more. In this blog, we’ll explore the fundamentals, properties, and types of binary trees. Let’s dive in!

Fig 2: The Black Family Tree

The Anatomy of Root, Child, and Leaf Nodes

In a tree structure, the Root Node branches out to Child Nodes, which may further extend or remain childless. Leaf Nodes are the endpoints without any children, typically at the tree’s surface level. A Parent Node is any node with one or more child nodes.

Fig 3: A Binary Tree

Other Terminologies

• Level: Rank of the node in a tree. The root node has level 0.
• Height: The longest path starting from the root node to the leaf node. Here,

• Degree: Maximum number of children that is possible for any parent node. The Binary Tree has a degree of 2.

Binary Tree

A Binary Tree is a specialized tree data structure where each node can have at most two children that means it has maximum degree of two.

Lemmata

1. The maximum number of possible nodes in a binary tree of height h is 2ʰ-1.
2. The minimum number of possible nodes in a binary tree is h whereas, h is the height of that tree.
3. The maximum number of possible nodes on level l of a binary tree is 2ˡ, whereas l ≥ 0.
4. The relation between the number of nodes, n, and edges, e is n = e + 1.
   (For non empty binary tree only)
5. The total number of binary trees possible with n number of nodes is:

Types of Binary Tree

• Full Binary Tree: A Full Binary Tree is characterized by each of its nodes having a degree of either 0 or 2. In simpler terms, in a Full Binary Tree, every node, except for the leaf nodes, has exactly two children.

Fig 4: A Full Binary Tree

• Complete Binary Tree: A Complete binary tree follows two key points:

1. The tree must fill to the left side first, which means; all nodes place as far left as possible.
2. All levels should fill up completely, except for the last level.

Fig 5: Complete vs incomplete Binary Tree

• Perfect Binary Tree: A Perfect Binary Tree has every internal node with exactly two children, forming a complete structure where all leaf nodes exist at the same depth.

Fig 6: A Perfect Binary Tree

Balanced Binary Tree: In a Balanced Binary Tree, the height difference between left and right sub-trees of any node is at most one. Iff, every node meets this condition, the tree is balanced.

Fig 7: Balanced Binary Tree

• Degenerated Binary Tree: A Degenerated Binary Tree is essentially a linked list, with all internal nodes having only one child. It is occasionally referred to as a skew binary Tree.

Fig 8: Degenerated Binary Tree

Binary Search Tree

A binary tree is called Binary Search Tree (BST) iff:

For each node N in the binary tree, T :

• All nodes in the left subtree of N have keys less than the key of N.
• All nodes in the right subtree of N have keys greater than the key of N.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7  13

We will write our binary search tree (BST) programs in Go. For quickly catch up you can rely on the Go basics.

Step 1: Define structure of a Node

Step 2: Root Node

Step 3: Insert function to add new data in the tree

Explanation: Using recursion, we are comparing data with the current node's value (node.data) to determine whether to insert on the left or right subtree, if values of the node smaller than the root node/ parent node then placed to the left and bigger values to the right. We have a terminal condition (data == -999) where recursion stops and returns to the previous node.

Step 4: Call the Insert Function to create a whole tree

This is the output in the console:

    10    
   / \
  5   20
 / \
3   6

Binary Tree Traversal

Binary Tree traversal is a process of traveling nodes of a binary tree. There are three common methods:

• In-order Traversal: In In-order Traversal the tree is first traversed from the far-most left side. It follows the following algorithm:
  
  Step A: Traverse the left subtree (recursively).
  Step B: Visit the current node.
  Step C: Traverse the right subtree (recursively).

    10    
   / \
  5   20
 / \
3   6

Inorder Taversal: 3, 5, 6, 10, 20
Time Complexity: O(N)

• Pre-order Traversal: Preorder traversal is a depth-first traversal algorithm used to visit all the nodes in a binary tree. Here is it’s algorithm:
  
  Step A: Visit the root.
  Step B: Traverse the left subtree.
  Step C: Traverse the right subtree.

    10    
   / \
  5   20
 / \
3   6

Pre-order Taversal: 10, 5, 3, 6, 20
Time Complexity: O(N)

• Post-order Traversal: In Post order Traversal first visit the left subtree, then the right subtree, and finally the root node:
  
  Step A: Traverse the left subtree
  Step B: Traverse the right subtree
  Step C: Visit the root

    10    
   / \
  5   20
 / \
3   6

Post-order Taversal: 3, 6, 5, 20, 10
Time Complexity: O(N)

Binary trees offer a diverse range of implementations and serve as the backbone for solving a variety of computational problems. Whether you’re building a file system, implementing an AI algorithm, or structuring a database, binary trees remain an essential tool in the programmer’s toolkit.

Keep learning!

repo: https://github.com/prcryx/BinaryTreeBlog