# Trees

A **tree** is a data structure that is made of nodes and pointers, much like a linked list. The difference between them lies in how they are organized:

In a linked list each node is connected to one “successor” node (via next pointer), that is, it is linear.

In a tree, the nodes can have several next pointers and thus are not linear.

The top node in the tree is called the **root** and all other nodes branch off from this one.

Every node in the tree can have some number of children. Each child node can in turn be the parent node to its children and so on.

A common example of a tree structure is the binary tree.

A **binary tree** is a tree that is limited such that each node has only two children.

If n1 is the root of a binary tree and n2 is the root of its left or right tree, then n1 is the **parent** of n2 and n2 is the **left **or** right child** of n1.

A node that has no children is called a **leaf**.

The nodes are **siblings** if they are left and right children of the same parent.

The level of a node in a binary tree:

- The root of the tree has level 0
- The level of any other node in the tree is one more than the level of its parent.

# Types of Binary Tree

**Strictly Binary Tree**

- If every non leaf node in a binary tree has non empty left and right sub trees, the tree is termed as strictly binary tree Every non leaf node has degree 2.
A strictly binary tree with n leaves has (2n-1) nodes.Thus a strictly binary tree has odd number of nodes.

**Complete Binary Tree**A complete binary tree of depth d is the binary tree of depth d that contains exactly^{ }2^{l}^{ }at each level*l*between 0 and d.Thus the total number of nodes in complete binary tree are 2^{d+1}-1 where leaf nodes are 2^{d }and non leaf are 2^{d}-1.Because a complete binary tree is also a strictly binary tree , thus if it has n leaves then it has 2n-1 nodes. Also follows from this is the previous assertion that if n=2^{d}then total nodes are**Atmost complete Binary Tree**A binary tree of depth d is an almost complete binary tree if:

- At any node in the tree with a right descendent at level d, node must have a left son and every left descendent of node is either a leaf at level d or has two sons.

i.e. the tree must be left filled.

**Note : A**CBT property says that if there are n nodes in the tree then leaf node have numbers

[(n/2)+1][(n/2)+2]———n

ACBT with n leaves has 2n nodes if it is not a SBT

An ACBT which is also an SBT has 2n-1 nodes for n leaves

Also an ACBT is an SBT if the number of node are odd

An ACBT of depth d is intermediate between the complete binary tree of depth, t d-1 that contains 2^{d-1} nodes , and the complete binary tree of depth d, which contains 2^{d+1}-1 nodes