Operation in Binary Tree

Every node in binary tree can have at most two children. Binary trees are mostly used in sorting and searching. In a balanced binary tree, there are roughly equal no. of nodes in the left and the right subtree. In a strictly binary tree, every non-leaf node in a binary tree has nonempty left and right sub-trees. Complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d. In an almost complete binary tree, every leaf is either at level d or d-1 and any node with right desc

Summary

Every node in binary tree can have at most two children. Binary trees are mostly used in sorting and searching. In a balanced binary tree, there are roughly equal no. of nodes in the left and the right subtree. In a strictly binary tree, every non-leaf node in a binary tree has nonempty left and right sub-trees. Complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d. In an almost complete binary tree, every leaf is either at level d or d-1 and any node with right desc

Things to Remember

  1. Every node in the binary tree can have at most two children.
  2. Binary trees are mostly used for sorting and searching. In a balanced binary tree, there are roughly equal no. of nodes in the left and the right subtree.
  3.  In a strictly binary tree, every non-leaf node in a binary tree has nonempty left and right sub-trees. 
  4. Complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d. 
  5.  In an almost complete binary tree, every leaf is either at level d or d-1 and any node with right descendant at level d must have a left son and every left descendant of the node is either a leaf at level d or has two sons.

MCQs

No MCQs found.

Subjective Questions

No subjective questions found.

Videos

No videos found.

Operation in Binary Tree

Operation in Binary Tree

Binary Tree

  • Every node in a binary tree can have at most two children.
  • A node can have only a left child or only a right child or it can have no children at all.
  • A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets.
  • The first subset contains a single element called the root of the tree.
  • The other two subsets are themselves binary trees, called the left and right subtree of the original tree. A left or right subtree can be empty.

Fig: Binary Tree
Fig: Binary Tree

Balanced Binary Tree

A binary tree is mostly used for sorting and searching.

Tree sorting & searching will be efficient if the tree is balanced, which means that there are roughly an equal number of nodes in the left & right subtree.

A binary tree is balanced if every level above the lowest is "full" (contains 2^n nodes).

Balanced trees have few levels and spread out widely.

fig: Balanced and Unbalanced Binary Tree
fig: Balanced and Unbalanced Binary Tree

Strictly Binary Trees(SBT)

If every non-leaf node in a binary tree has nonempty left and right sub-trees, the tree is called a strictly binary tree.

A strictly binary tree with n leaves always contains 2n - 1 nodes.

Fig: Strictly Binary Tree
Fig: Strictly Binary Tree

Complete Binary Tree (CBT)

Complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d. In CBT, every leaf should be at same level. CBT also called Full Binary Tree: A full binary tree is a binary tree where all the leaves are on the same level and every non-leaf has two children.
The height (or depth ) h of CBT is O(log n).
Proof:
In the case of CBT, The total number of nodes = the sum of the number of nodes at each level between 0 and d.
The number of nodes n is n=1+2+2^2+2^3+…+2^h =2^(h+1)-1
Therefore, 2^(h+1) = n+1 ==> h=log(n+1)-1
Hence, h=O(log n)
fig: Complete Binary Trees
fig: Complete Binary Trees

Almost Complete Binary Tree

A binary tree of depth d is an almost complete binary tree if:

  1. Each leaf in the tree is either at level d or d-1
  2. For any node “nd” in the tree with a right descendant at level d, “nd” must have a left son and every left descendant of “nd” is either a leaf at level d or has two sons.
Fig: Almost Complete Binary Tree
Fig: Almost Complete Binary Tree

References

1. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

2. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”



Lesson

Trees

Subject

Computer Engineering

Grade

Engineering

Recent Notes

No recent notes.

Related Notes

No related notes.