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.
A node is an element of the tree. A node in a tree can have any number of children.
A root is a node without any parent element. There can be only one root node in a tree.
An edge is a link between two nodes.
A node without any children is called a leaf node.
Children of same parent are called siblings.
All nodes that come in the path between root and itself are called ancestors.
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 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 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.
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.
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.
- An n-ary tree where characters are stored at each node.
- Each path down the tree may represent a word.
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.