Tree in Data Structure:

 Tree can be defined as a

collection of entities/nodes which are linked together to

simulate a hierarchy.

Root node

T

Root: where we doesn’t have parent node.

Node: node contains some information and also contain link to

another node.

Parent Node: The immediate predecessor of any node.

Child Node: The immediate successor of a node is called lild of

that particular node.

A

B C D

E F G H

I J K L M

Leaf Node: external nodes (No child)

Non leaf nodes : internal nodes: (those have child nodes)

Path: sequence of steps constructive edges from source to

destination.

Ancestor and Descendant:

Sub Tree: Sub-tree of any tree T is defined in

which it is containing a node of tree T and all its

descendant.

Sibling and Degree of Tree:

Depth of a node: length of a path from root to that node.

Height of a Node: Calculated to the path from

Tree is having n nodes and n-1 edges will exist.

Representation of tree:

A

B C

D E F

LEFT Right

Binary tree and its types : atmost 2 (two) chlidren

which is a example of binary tree?

A

B NULL C

NULL F NULL NULL D NULL NULL E NULL

Representation (Logical Representaton)

Types of Binary tree

 Full Binary Tree (Where each node contains

eirthrt ‘0’ or two (2) child or each node contains

exactly two child except leaf nodes.

 Complete binary tree: if all the levels are

completely filled (except possibly the last level)

and the last level has nodes as left as possible.

Examples of full binary tree or not

Complete binary tree or not

Is it complete

Binary tree?

Properties: no of leaf nodes=no of internal nodes +

1 (10+1=11)

Extended binary tree (2 tree)

A binary tree T is said to be 2 tree or extended

binary tree if each node has either 0 or 2 children. A

binary tree can be converted into 2 tree by

replacing each empty node/subtree by a new node.

Internal Nodes External Node

Relationship between nodes:

External node = internal nodes + 1

Path Length in extended binary tree:

Internal path = calculate no of edges from root to a

particular node (internal)

0+1+2+1+2+3 = 9

External path : 21

Relation = external path length = internal path

length +2*n = 9 +(2*6) = 21

Note : n is a number of internal nodes :

Properties of Binary tree:

The maximum nodes possible at any level are 2 n

The maximum nodes possible at height h = 2 h+1 -1

2 0 +2 1 +2 2 +………….+2 h (GP SERIES)

The minimum numbers of nodes possible at height

h = h+1

Problem : Suppose we have n maximum nodes in

binary tree then find possible height:

n = 2 h+1 -1

n+1=2 h+1

log(n+1)=log( 2 h+1)

if n=0

log(1)

log(2)

log(n)

h= log (n+1)-1 (ceiling function)