[go: up one dir, main page]
Scribd
Upload
53 views2 pages

Binary Trees Notes With Table

Binary trees are defined as trees with nodes having at most two children, with various types including full, complete, perfect, and degenerate trees, each having specific properties and node counts. A full binary tree has nodes with either zero or two children, while a complete binary tree fills all levels except the last from left to right. Degenerate trees have nodes with only one child, resembling a linked list structure.

Uploaded by

medhideas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
53 views2 pages

Binary Trees Notes With Table

Binary trees are defined as trees with nodes having at most two children, with various types including full, complete, perfect, and degenerate trees, each having specific properties and node counts. A full binary tree has nodes with either zero or two children, while a complete binary tree fills all levels except the last from left to right. Degenerate trees have nodes with only one child, resembling a linked list structure.

Uploaded by

medhideas
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Binary Trees - Notes

Definition and Basic Properties of Binary Trees

- A binary tree is a tree where each node has at most two children, called left and right child.

- The height of a binary tree is the length of the longest path from the root to a leaf node.

- The maximum number of nodes at level i in a binary tree is 2^i.

- The maximum number of nodes in a binary tree of height h is given by: sum of 2^i from i=0 to h = 2^(h+1) - 1.

- The minimum number of nodes in a binary tree of height h is at least h + 1.

Full (Proper or Strict) Binary Tree

- A full binary tree is a binary tree where each node has either zero or two children.

- Leaf nodes = Internal nodes + 1.

- Max nodes: 2^(h+1) - 1.

- Min nodes: 2^h.

Complete Binary Tree

- A complete binary tree is a binary tree in which all levels are completely filled except possibly the last.

- Last level is filled from left to right without gaps.

- Max nodes: 2^(h+1) - 1.

- Min nodes: 2^h.

- Height: h = ceil(log2(n+1)) - 1.

Perfect Binary Tree

- A perfect binary tree is a full binary tree where all leaf nodes are at the same level.

- All internal nodes have exactly two children.

- Every perfect binary tree is both full and complete.

Degenerate (Skewed) Binary Tree

- A degenerate binary tree is a tree where every internal node has exactly one child.

- Left skewed: all nodes have only left children.

- Right skewed: all nodes have only right children.


Binary Trees - Notes

- Can mix left and right skewed, still one child per internal node.

Representation of Binary Trees in Memory

- Each node stores data and may have pointers to its left and right children.

- If a child is absent, the pointer is null.

- Nodes are dynamically created and linked.

Important Note

- In a complete binary tree, nodes at the last level must be filled from left to right without gaps.

- Violating this by filling right child before left at the last level is incorrect.

Comparison Table

Type of Binary Tree Definition Key Properties Node Count (Height = h)

Full Binary Tree Each


Leaf
Max:
nodes
node
2^(h+1)
has
= Internal
0 -1
or 2 nodes
children
+1

Min: 2^h

Complete Binary Tree All levels filled except last; last

level level
Last filled nodes
left to right
as left as

possible
Max: 2^(h+1) -1

Min: 2^h

Perfect Binary Tree Full binary tree with all leaves

at same
BothMax:
full level
and
2^(h+1)
complete
-1 (exact)

Degenerate Tree Each internal node has one

Skewed
child
Min: h+1
like linked
(linear)list

You might also like