Tree Data structure — Part-2

Binary Trees

“Hey There”, We have explored the basic terms associated with Tress and introduced to Binary Tree in our previous article (Tree Data structure — Part-1). If you have not gone through that 3 minutes read, I recommend you to visit the article at below link:

Tree Data structure— Part-I

Now let’s explore the below topics on the Binary Tree in this article:

1. Unlabelled and Labeled Nodes (will help in constructing BTrees)
2. Formula to calculate No of Binary trees from given no of Nodes
3. Height vs Nodes in Binary Tree
4. Internal Nodes vs External Nodes in BinaryTree
5. Different Kinds of Binary Trees.

Unlabelled Nodes: The empty nodes or nodes having no labels/data with them are known as unlabelled nodes.

Labeled Nodes: The nodes having labels/data with them are known as labeled nodes.

“Generally will have trees with either labeled or unlabelled nodes. but not a mix of both.”

Binary Tree with Unlabelled Nodes#

Let’s suppose given three unlabelled nodes, then we can make the following different Binary Trees

Unlabelled Binary Trees

So from the above diagram, we can make a formula to calculate the number of binary trees formed from unlabelled nodes.

T(3) = 5 (from above example)

likewise,

T(4) = 14 ways

T(5) the = 42 ways

To find all different unlabelled trees formula will be :

Also called as Catalin Number

So if we have labeled nodes, we can use the above T(n) Catalin number formula to calculate the no of ways to form a labeled binary tree.

‘n!’, denotes the no of different ways labeled nodes can be arranged (permutation) of filling.

T(3) = 5 * 3! = 30 ways (5 * 6)

T(5) = 42 * 5! = 5040 ways (42 * 120)

Above Catalin number gives us basic value for Btree count with only unlabelled nodes and multiplying with n! will give the labeled BTree count

“Above formulas will be helpful later while performing operations on a binary tree”

Height(H) vs Nodes(N) in Binary Tree:

The relation between binary tree nodes and height is :

“A BTree with minimum height will be filled with max no of nodes, and with Maximum height, it will be filled with minimum no of nodes”

Minimum no of Nodes N = H + 1

Maximum no of Nodes N = (2^H+1) -1

alternative relation is :

Minimum Height H = N-1

Maximum Height H = Log (N+1) -1

For example from the below diagrams:

In the above BTree with height 1, min no of nodes required is 2 and max can be 3

Minimum no of Nodes N = 1 + 1 = 2

Maximum no of Nodes N = 2² - 1 = 3

In the above BTree with height 2, min no of nodes required is 3 and max can be 15

Minimum no of Nodes N = 2 + 1 = 3

Maximum no of Nodes N = 2⁴ -1 = 15

So Height(h) Range of a Binary Tree :

Log(n+1)- 1 ≤ h ≤ n - 1

This is why traversing the BTree from root to down (max Depth) will always have a Time Complexity range of O(log n) to O(n).

or Minimum height is O(log n), and Maximum is O(n).

Number of Nodes in a Binary Tree:

h+1 ≤ n ≤ 2^(h+1)-1

So when required to traverse all nodes or parts (subtrees) in a binary Tree, the Time complexity range will be O(h) to (2^h) i.e Exponential of 2 with height and Linear with no of nodes.

Note “ Used h: as a parameter here, so as not to get confused with previous notation.”

The above formulas and complexity notations will help us while analyzing BTree operations.

Internal Nodes vs External Nodes in BinaryTree#

Let’s find out one more relationship between internal nodes and leaf nodes with the degrees.

I. The first tree from above has the following degrees (node):

Degree(0) — 2

Degree(1) — 2

Degree(2) — 1

I. The second tree from above has the following degrees (node):

Degree(0) — 3

Degree(1) — 5

Degree(2) — 2

For the above values, there is a relation between internal-external nodes i.e

deg(0) = deg(2) + 1 this always true with binary Trees

Different Kinds of Binary Trees#

Complete or Perfect or Strict Binary Tree:

• All the levels are completely filled except possibly the last one
• Nodes at the last level are as far left as possible
• The degree of all internal nodes is always 2, and leaf nodes 0
• Following is the relation between nodes and the height of CBT (Complete Binary Tree)

Binary Search Tree#

A Binary Search Tree, also known as an ordered Binary Tree, is a variant of a Binary Tree with a strict condition based on node value.

For all the nodes in a BST, the values of all the nodes in the left sub-tree of the current node are less than or equal to the value of the node itself. All the node values in the right subtree are greater than the value of the current node. This is referred to as the BST rule.

NodeValues(LeftSubtree)≤ CurrentNodeValue< NodeValues(RightSubTree)

Different b/w Binary Search Tree and Binary Tree#

Not every Binary Tree is a Binary Search Tree. BST is simply a type of Binary Tree. For a Binary Tree to qualify as a Binary Search Tree, it needs to follow the general rule which we covered earlier.

Let’s see an example to understand why every Binary Tree is not always a Binary Search Tree?

As you can see in the above figure, the first one is a Binary Tree because each node has a maximum of two children. But why isn’t it a Binary Search Tree? Because it does not follow the BST rule that Node 2 cannot be a left child of Node 1, and we would need to make Node 1 a left child of Node 2 to convert it into a Binary Search Tree.

Now that we have studied a Binary Search Tree and how it’s different from a simple Binary Tree, it is time to represent, and implement the basic operations –Insert(), Search() and Delete()–to see how efficient this BST is compared to a simple Binary Tree. We can use Arrays or a Linked List to represent the Binary Trees.

Next articles for detailed implementation of Binary Search Trees:

https://medium.com/@tirupatirao_87921/binary-search-tree-25e3bc179968

Thank for reading and giving 👏👏👏, will see you in the next read 🙂

#arraysinjava. #array #datastructures #codinginterviewquestions #codinginterview #faang #leetcode #animated #java #python #faang #motion