{{announcement.body}}
{{announcement.title}}

Understanding Binary Trees Part 1

DZone 's Guide to

Understanding Binary Trees Part 1

In this article, we work to understand the basic concepts of binary trees, including their properties and types.

· Java Zone ·
Free Resource

Quick recap of some basic tree vocabulary, before getting in depth into this series of Binary Trees... 

What Is a Tree?

Unlike Arrays, Linked Lists, Stack, and Queues, which are linear data structures, trees are hierarchical data structures. Trees represent non-linear data structures and can be defined as collection of entities called “Nodes” linked together to simulate hierarchy. In other words, Tree is a widely used abstract data type (ADT) that simulates a hierarchical tree structure

Important Tree Glossary:

Binary tree data structure

  • Root: Node without any parent. Topmost node of a tree
  • Children: Immediate successor nodes
  • Siblings: Children of same parent
  • Leaf node: Any node that doesn’t have any children
  • Internal Nodes: All nodes with at least one child
  • Depth of Node x: Length of path from root to Node x
  • Height of Node x: Number of edges in the longest path from node x to leaf node
  • Height of tree: Height of the tree is the height of the root
  • Level of node: Set of all nodes at a given depth is called the level of the tree

Key Properties:

  • Trees with N nodes will have N-1 edges
  • Depth of root node is Zero
  • Root node is at level Zero
  • Height of leaf node is Zero
  • Height of tree with one node is Zero
  • Every node except root is connected by a directed edge from exactly one node to other node and direction is: parent -> children

Now, having understood the fundamentals of trees, let us get into this series of Binary Trees

So, What Is a Binary Tree?

A tree is called a binary tree if each node has either 

  • Zero,
  • One, or Node in binary tree
  • Two children

An empty tree is also a valid binary tree. 

We can visualize a binary tree as consisting of a root and two disjoint binary trees called left and right subtrees of the root.

Examples of Binary trees:

Binary tree examples

Difference between a Tree and Binary Tree:

Difference between binary and general tree

Properties of Binary Tree      

  • Maximum number of nodes of binary tree of height “h” is 2h+1 - 1

maximum number of nodes in a binary tree

  • Minimum number of nodes of binary tree of height “h” is “h+1”

minimum number of nodes in binary tree

  • Minimum height of the binary tree of with maximum number of nodes as “n”  

For any binary tree of height “h”, maximum number of nodes = 2h+1 – 1
Here, Max nodes = n
So, n = 2h+1 – 1

=> n + 1 = 2h+1 

Applying log on both sides,

=>log(n+1) = log2h+1 

=> log(n+1) = (h+1) log2

=>log(n+1)=(h+1)

=>Height of the binary with maximum “n” nodes => h = ⌈ log(n+1) ⌉ - 1

  • Minimum height of the binary tree of with maximum number of nodes as “n” 

For any binary tree of height “h”, minimum number of nodes = h + 1

=>n=h+1

=>Height of the binary with minimum “n” nodes => h = n-1

Types of Binary Trees

The following are common types of Binary Trees:

Full/Strict Binary Trees:

A full binary tree is called a binary tree in which each node has exactly

  • Zero or
  • Two children
  • In a full binary tree, number of leaf nodes = No. of internal nodes + 1

Full binary tree

Properties of full binary tree:

  • Maximum number of nodes of full binary tree of height “h” is 2h+1 – 1
  • Minimum number of nodes of full binary tree of height “h” is 2h+1

Properties of full binary tree

  • Minimum height of the full binary tree of with maximum number of nodes as “n” is ⌈ log(n+1) ⌉ - 1
  • Maximum height of the binary tree of with minimum number of nodes as “n”

For any binary tree of height “h”, minimum number of nodes = 2h + 1

=>n=2h+1

=>Height of the binary with minimum “n” nodes => h = (n-1)/2

Complete Binary Tree

A binary tree is called a complete binary tree if all levels except possibly the last is completely filled and all the nodes in the last level are as left as possible.

Examples of complete binary trees:

Complete binary tree

Properties of complete binary tree:

  • Maximum number of nodes of complete binary tree of height “h” is 2h+1 – 1
  • Minimum number of nodes of complete binary tree of height “h” - 2h 

  • Minimum height of complete binary tree of with maximum number of nodes as “n” ⌈ log(n+1) ⌉ - 1
  • Maximum height of complete binary tree of with minimum number of nodes as “n”

For any binary tree of height “h”, minimum number of nodes = 2h

=>log(n) = log2h

=> log(n) = (h)log2

=>h = log(n)

=>Height of the binary with minimum “n” nodes => h = log(n)

To conclude, 

 

Max Nodes Min Nodes

Binary Tree

2h+1 – 1

h+1

Full Binary Tree

2h+1 – 1

2h+1

Complete Binary Tree

2h+1 – 1

2h

If maximum and minimum nodes are given, height of the tree is 

 

Minimum Height

Max Height

Binary Tree

⌈ log(n+1) ⌉ - 1

n-1

Full Binary Tree

⌈ log(n+1) ⌉ - 1

(n-1)/2

Complete Binary Tree

⌈ log(n+1) ⌉ - 1

log(n)

Perfect Binary Tree

A binary tree is called perfect if all the internal nodes have two children (exactly two children) and all the leaf nodes are at same level. A perfect binary tree can also be a full binary tree or a complete binary tree but not vice versa.

Perfect binary tree

Degenerate Binary Tree

  • All the internal nodes have only one child except leaf nodes. 
  • If every node in the tree has only one left child, it is left skewed
  • If every node in the tree has only one right child, it is right skewed

Degenerate binary tree

Balanced Binary Tree

A balanced binary tree is a binary tree structure in which the left and right sub-trees of every node differ in height by no more than 1. Balanced Binary Search trees like AVL Trees, Red-Black Trees are some of the examples

So, in this part, we have understood basic concepts of trees, binary tree, its properties and types. In my next upcoming article, we go deeper into binary tree concepts, applications, traversals, representations and implementations.

Stay tuned!!!

Topics:
binary tree, data structure courses, theory

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}