What is a Binary Tree Data Structure ? (with Diagram) | Introduction | DSA

Binary Tree Data Structure –

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child(LC) and the right child(RC).

Binary tree (Logical Diagram) –

Important Binary Tree Terms & Properties –

• A binary tree is called STRICT/PROPER binary tree when each node has 2 or 0 children.
• A binary tree is called COMPLETE binary tree if all levels except the last are completely filled and all nodes are as left as possible.
• A binary tree is called PERFECT binary tree if all levels are completely filled with 2 children each.
• Max number of nodes at a given level ‘x’ = 2^x
• For a binary tree, maximum number of nodes with height ‘h’ = 2^(h+1) – 1
• A binary tree is called BALANCE binary tree, if the difference between the height of left subtree and right subtree for every node is not more than k(usually k=1)

Binary Tree Implementation view (Dynamic Nodes in Memory) –

Binary Tree Implementation view (Array Implementation) –

Sparse vs Dense Binary Tree –

• A dense binary tree is close to perfect (it has close to 2^(h + 1) – 1 nodes)
• A sparse binary tree is closer to a linked list (it has close to h nodes)

YouTube video tutorial –