Tree
Tree
Properties
- Every tree has a special node called the root node. The root node can be used to traverse every node of the tree. It is called root because the tree originated from root only.
- If a tree has N nodes(vertices), the number of edges is always one less than the number of nodes (i.e., N-1). If it has more than that, it’s called a graph not a tree.
- Every child has only a single Parent but Parent can have multiple children.
Terminology
- The
depthof a node is the number of edges from the node to the tree’s root node. A root node will have a depth of 0. - The
heightof a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.
Types of Trees
General Tree
A Tree without any constraint imposed on the hierarchy of the tree is called a general tree.
Each node can have an infinite number of children.
This is the super-set of all other types of trees.
Binary Tree
Binary Tree is the type of tree in which each parent can have at most two children.
Check Binary Tree for more details
Binary Search Tree
BST is an extension of BT with some added constraints.
In BST, the value of the left node must be smaller than the parent node, and the value of the right node must be greater than the parent node.
AVL Tree
AVL Tree is a self-balancing binary tree.
In AVL tree, the heights of children’s node differ at most 1 (i.e., the valid balancing factor in AVL tree are 1, 0 and -1). When a new node added to a tree and tree becomes unbalanced, rotation is done to make a tree balanced.
N-ary Tree
In N-ary Tree, the maximum number of children that a node can have is limited to N.
Tries
It is commonly used to represent a dictionary for looking up words in a vocabulary
For example, when implementing a search bar with auto-completion or query suggestion, “trie” is needed to look up words starting with the characters input by the user quickly
Check Tries for the implementation
References
Types of Trees in Data Structure
