A tree is a data structure used to represent hierarchical structures. A file system is an example of a hierarchical structure, where one folder can have subfolders, they can again have sub folders and so on. A tree is a non-linear data structure.

**BASIC TERMINOLOGIES**

**Node**

A **node **is an element of the tree. A node in a tree can have any number of children.

**Root**

A root is a node without any parent element. There can be only one root node in a tree.

**Edge**

An edge is a link between two nodes.

**Leaf**

A node without any children is called a leaf node.

**Siblings**

Children of same parent are called siblings.

**Ancestor**

All nodes that come in the path between root and itself are called ancestors.

**Descendants**

All children, their children and so on which can be reached from a node are called descendants of a node. Size of a node is the number of all descendants including it.

**Depth**

Depth of a node is the length of path from root to that node.

**Depth of a tree** is the depth of the node with maximum depth.

**Height**

Height of a node is the length of path from a node to the deepest descendant node which can be reached from that node.

**Height of a tree** is the maximum height among all nodes in a tree.

**Level**

Set of all nodes at a given depth is called a level. For instance, root is at level 0 and all its immediate children are at level 1.

**Skew trees**

Every node except leaf node has only one child.

**Left skew tree**

Every node except root has only one left child.

**Right skew tree**

Every node except root has only one right child.

**Trie**

- An n-ary tree where characters are stored at each node.
- Each path down the tree may represent a word.

**TREE OPERATIONS**

**Balancing a Tree**

- The depth of subtree will not vary by more than a certain amount.
- Does not mean that left and right sub trees are exactly same size.

**REFERENCES: **

http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf