1.

Binary TREE

 Root: node without parent (A)

 Siblings: nodes share the same parent
 Internal node: node with at least one child (A, B, C, F)
 External node (leaf ): node without children (E, I, J, K, G, H, D)
 Ancestors of a node: parent, grandparent, grand-grandparent, etc.
 Descendant of a node: child, grandchild, grand-grandchild, etc.

2. Degree of a NODE vs Degree of a TREE

In Data Structures and Algorithms (DSA), the degree of a tree is defined as:

The maximum degree of any node in the tree, where the degree of a node is the number of its immediate children.

Analyzing the Given Tree:

Let’s look at each node’s degree in the image:

 Node A → 3 children (B, C, D) → Degree 3

 Node B → 2 children (E, F) → Degree 2
 Node C → 2 children (G, H) → Degree 2
 Node D → 0 children → Degree 0
 Node E → 0 children → Degree 0
 Node F → 3 children (I, J, K) → Degree 3
 Nodes G, H, I, J, K → 0 children → Degree 0

 ✅ Maximum degree among all nodes = 3

 🔷 Therefore, the degree of the tree is 3.
 Let me know if you'd like the height or depth of the tree as well!
 1. Degree of a NODE vs Degree of a TREE

 Depth of x = no of edges in path from root to x. {we will travel from the particular node to Root node}
 Height of x= no of edges in longest path from x to a leaf. (down-ward) {we will travel from the particular node to Leaf node following longest path}

✅ Depth (D) – Labeled on the Left

 Depth is the number of edges from the root to the node.

 Labels:

o D0 for A → ✅ Root node has depth 0

o D1 for B and C → ✅ One edge from A
o D2 for E, F, G, H → ✅ Two edges from A
o D3 for I, J, K → ✅ Three edges from A

✅ Height (H) – Labeled on the Right

 Height is the number of edges on the longest path from a node to a leaf.

 Labels:

o H0 for I, J, K → ✅ Leaf nodes have height 0

o H1 for F, G, H → ✅ One level above leaves
o H2 for D → ✅ Leaf node itself, but the label here seems incorrect (see note below)
o H3 for A → ✅ Longest path from A to any leaf is 3 edges

🧠 Summary:

Node Dept Height

h

A 0 3

B, C 1 2 (B), 1 (C)

D 1 0

E, F, G, H 2 1 (F), 0 (others)

I, J, K 3 0

✅ Final Verdict:

The concepts are mostly correct in the image, with a minor mistake in height labeling for node D. Otherwise, it’s a great visual for understanding height vs. depth.

Let me know if you want a corrected version!

Types of Binary Trees-
Binary trees can be of the following types-

1. Rooted Binary Tree

2. Full / Strictly Binary Tree
3. Complete / Perfect Binary Tree
4. Almost Complete Binary Tree
5. Skewed Binary Tree

1. Rooted Binary Tree-

A rooted binary tree is a binary tree that satisfies the following 2 properties-

 It has a root node.

 Each node has at most 2 children.

Example-
2. Strictly Binary Tree-

 A binary tree in which every node has either 0 or 2 children is called as a Full binary tree.
 Full binary tree is also called as Strictly binary tree.

Example-

Here,

 First binary tree is not a full binary tree.

 This is because node C has only 1 child.

A Binary tree having ‘h’ height can have maximum ‘n’ nodes:
h+1
n=2 −1

Example:

If a binary tree has height ‘h’=3 then number of nodes:

h+1
n=2 −1
3+1
n=2 −1
n = 7 nodes

3. Perfect Binary Tree-

A complete binary tree is a binary tree that satisfies the following 2 properties-

 Every internal node has exactly 2 children.

 All the leaf nodes are at the same level.

Complete binary tree is also called as Perfect binary tree.

Example-

Here,

 First binary tree is not a complete binary tree.

 This is because all the leaf nodes are not at the same level.

4. Complete Binary Tree-

An almost complete binary tree is a binary tree that satisfies the following 2 properties-

 All the levels are completely filled except possibly the last level.
  The last level must be strictly filled from left to right.

Example-

Here,

 First binary tree is not an almost complete binary tree.

 This is because the last level is not filled from left to right.

5. Skewed Binary Tree-

A skewed binary tree is a binary tree that satisfies the following 2 properties-

 All the nodes except one node has one and only one child.
 The remaining node has no child.

OR

A skewed binary tree is a binary tree of n nodes such that its depth is (n-1).

Example-
Tree Terminology-
The important terms related to tree data structure are-

1. Root-

 The first node from where the tree originates is called as a root node.
 In any tree, there must be only one root node.
 We can never have multiple root nodes in a tree data structure.

Example-

Here, node A is the only root node.

2. Edge-

 The connecting link between any two nodes is called as an edge.

 In a tree with n number of nodes, there are exactly (n-1) number of edges.

Example-
3. Parent-

 The node which has a branch from it to any other node is called as a parent node.
 In other words, the node which has one or more children is called as a parent node.
 In a tree, a parent node can have any number of child nodes.

Example-

Here,

 Node A is the parent of nodes B and C

 Node B is the parent of nodes D, E and F
 Node C is the parent of nodes G and H
 Node E is the parent of nodes I and J
 Node G is the parent of node K

4. Child-

 The node which is a descendant of some node is called as a child node.

 All the nodes except root node are child nodes.

Example-

Here,

 Nodes B and C are the children of node A

 Nodes D, E and F are the children of node B
 Nodes G and H are the children of node C
 Nodes I and J are the children of node E
 Node K is the child of node G

5. Siblings-
 Nodes which belong to the same parent are called as siblings.
 In other words, nodes with the same parent are sibling nodes.

Example-

Here,

 Nodes B and C are siblings

 Nodes D, E and F are siblings
 Nodes G and H are siblings
 Nodes I and J are siblings

6. Degree-

 Degree of a node is the total number of children of that node.

 Degree of a tree is the highest degree of a node among all the nodes in the tree.

Example-

Here,

 Degree of node A = 2
 Degree of node B = 3
 Degree of node C = 2
 Degree of node D = 0
 Degree of node E = 2
 Degree of node F = 0
 Degree of node G = 1
 Degree of node H = 0
 Degree of node I = 0
 Degree of node J = 0
 Degree of node K = 0

7. Internal Node-
  The node which has at least one child is called as an internal node.
 Internal nodes are also called as non-terminal nodes.
 Every non-leaf node is an internal node.

Example-

Here, nodes A, B, C, E and G are internal nodes.

8. Leaf Node-

 The node which does not have any child is called as a leaf node.
 Leaf nodes are also called as external nodes or terminal nodes.

Example-

Here, nodes D, I, J, F, K and H are leaf nodes.

9. Level-
  In a tree, each step from top to bottom is called as level of a tree.
 The level count starts with 0 and increments by 1 at each level or step.

Example-

10. Height-

 Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node.
 Height of a tree is the height of root node.
 Height of all leaf nodes = 0

Example-

Here,

 Height of node A = 3
 Height of node B = 2
 Height of node C = 2
 Height of node D = 0
 Height of node E = 1
 Height of node F = 0
 Height of node G = 1
 Height of node H = 0
 Height of node I = 0
 Height of node J = 0
 Height of node K = 0

11. Depth-

 Total number of edges from root node to a particular node is called as depth of that node.
  Depth of a tree is the total number of edges from root node to a leaf node in the longest path.
 Depth of the root node = 0
 The terms “level” and “depth” are used interchangeably.

Example-

Here,

 Depth of node A = 0
 Depth of node B = 1
 Depth of node C = 1
 Depth of node D = 2
 Depth of node E = 2
 Depth of node F = 2
 Depth of node G = 2
 Depth of node H = 2
 Depth of node I = 3
 Depth of node J = 3
 Depth of node K = 3

12. Subtree-

 In a tree, each child from a node forms a subtree recursively.

 Every child node forms a subtree on its parent node.

Example-

13. Forest-

A forest is a set of disjoint trees.

 Example-

To gain better understanding about Tree Terminology,

Properties of Binary Trees

1. Maximum Nodes at Level 'l'
A binary tree can have at most 2l nodes at level l.
 Level Definition: The number of edges in the path from the root to a node. The root is at level 0.
 Proof by Induction:
Base case: For root (l = 0), nodes = 20 = 1.
Inductive step: If level l has 2l nodes, then the next level has at most twice as many:
2×2l = 2l+1

2. Maximum Nodes in a Binary Tree of Height 'h'

A binary tree of height h can have at most 2h+1 - 1 nodes.
 Height Definition: The longest path from the root to a leaf node. Please note that a tree with only one root node is
considered to have height 0 and an empty tree (or root is NULL) is considered to have height "-1"
Formula Derivation: A tree has the maximum nodes when all levels are completely filled. Summing nodes at each
level:
1 + 2 + 4 +...+ 2h = 2h+1 - 1
 Alternate Height Convention: Some books consider a tree with only one root node is considered to have height 1
and an empty tree (or root is NULL) is considered to have height 0. making the formula 2h - 1.


The minimum possible height for N nodes is ⌊log⁡2N⌋.

3. Minimum Height for 'N' Nodes

Explanation: A binary tree with height h can have at most 2h+1 - 1 nodes.
Rearranging:
N ≤ 2h+1 − 1
2h+1 ≥ N+1

h ≥ ⌊log2N⌋
h ≥ log2(N+1) - 1 (Taking log2 both sides)

This means a binary tree with N nodes must have at least ⌊log⁡2N⌋ levels.

A binary tree with L leaves must have at least ⌊log⁡2L⌋ levels.

4. Minimum Levels for 'L' Leaves

Why? A tree has the maximum number of leaves when all levels are fully filled.
From Property 1:
L ≤ 2l ( l is the level where leaves appear)

lmin = ⌊log⁡2L⌋
Solving for l:
This gives the minimum levels needed to accommodate L leaves.

5. Nodes with Two Children vs. Leaf Nodes

In a full binary tree (where every node has either 0 or 2 children), the number of leaf nodes (L) is always one more
than the internal nodes (T) with two children:
L=T+1
Proof:
A full binary tree has a total of 2 h+1 - 1 nodes.
Leaves are at the last level: L = 2 h.
Internal nodes: T =2 h (2−1) − 1= 2h - 1.
Simplifies to L=T+1

6. Total Edges in a Binary Tree

In any non-empty binary tree with n nodes, the total number of edges is n - 1.
Every node (except the root) has exactly one parent, and each parent-child connection represents an edge.
Since there are n nodes, there must be n - 1 edges.

Tree Traversals:

 Preorder Traversal: Preorder traversal visits the node in the order: Root (1) -> Left (2) -> Right (3): 1 – 2 – 3

 In-order Traversal: In-order traversal visits the node in the order: Left (2) -> Root (1) -> Right (3) : 2 – 1 – 3

 Post-order Traversal: Post-order traversal visits the node in the order: Left (2) -> Right (3) -> Root (1): 2 – 3 – 1
Example 1:

Example 2:

 Pre-order: A, L, O, D, G, A, I, L, Y
 In-order: O, L, D, A, A, G, L, I, Y
 Post-order: O, D, L, A, L, Y, I, G, A

https://www.youtube.com/watch?v=uI77Ij5Kiic
Udemy: 295 – Can we generate tree from Traversals

Udemy: 296 - Generate Tree from Traversals