Trees

Trees

In this blog, we will discuss the Tree as a part of Graph, as well as Tree traversal algorithms and Special types of trees. The tree data structure is used to present a hierarchical relationship between the data. The elements of the tree are called nodes. Starting from the root (initial) node, each node has a certain number of children. The nodes higher in the hierarchy are called the parent nodes and the children are called the child nodes. The nodes having the same parent are called siblings. The node with no child node is called a leaf node. The level of a node is the depth of the tree from that node to the root node. Since the tree is a hierarchical structure, the child node at one level can act as the parent node for the nodes at the next level.

The tree in which each node has a maximum of 2 child nodes is called a Binary tree. Nodes of a binary tree can be represented using a structure or a class consisting of node information and a pointer each for the left and the right child node. The process of accessing the elements of a tree is called tree traversal. There are 4 types of tree traversal algorithms:

1. Inorder traversal:

For Inorder traversal, the left subtree of a node is accessed first followed by the value of the node and then the right subtree of the node. For example, consider the following tree.

 

The Inorder traversal of the tree in Fig 1 will be 8,4,9,2,10,5,11,1,12,6,13,3,14,7,15.

2. Preorder traversal:

For Preorder traversal, the value of the node is accessed first followed by the left subtree of a node and then the right subtree of the node.

The Preorder traversal of the tree in Fig 1 will be 1,2,4,8,8,5,10,11,3,6,12,13,7,14,15.

3. Postorder traversal:

For Postorder traversal, the left subtree of the node is accessed first followed by the right subtree of a node, and then the value of the node.

The Postorder traversal of the tree in Fig 1 will be 8,9,4,10,11,5,12,13,6,14,15,7,3,1. 

4. Level order traversal:

For Level order traversal, starting from the root node, the nodes at a single level are accessed first before moving to the next level. Level order traversal is also Breadth-first traversal (BSF).

The Level order traversal of the tree in Fig 1 will be 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15.

Binary Search Tree can also be converted to a doubly linked list such that the nodes of the doubly linked list are placed according to the inorder traversal of the tree.

Special types of trees:

1. Binary Search Trees:

Binary search tree (BST) is a special type of tree in which the nodes are sorted according to the Inorder traversal. The search time complexity in a binary tree is O(log n). Insertion in a BST is achieved by moving to the left subtree if the value of the node to be inserted is lower than the current node or by moving to the right subtree if the value of the node to be inserted is greater than the current node. This process is repeated until a leaf node is found.

2. AVL Trees:

AVL trees are BSTs in which for each node, the difference between the max level of the left subtree and the max level of the right subtree is not more than 1. AVL trees are also called the self-balancing BST’s.

3. Red Black Trees:

Red Black trees are BSTs in which the nodes are colored either black or red with the root node always being black. No adjacent nodes in a Red Black tree can be red and for each node, any path to a leaf node has the same number of black nodes. Like AVL trees, Red Black trees are also self-balancing BSTs.

4. Trie:

Trie is a special type of independent data structure which is in the form of a tree. It is generally used for string processing. Each node in a Trie has 26 child nodes indicating one of 26 English characters. Trie also has a Boolean data element marking the end of a string. The structure of a Trie can differ to incorporate various use cases.

5. Threaded Binary Trees:

Threaded binary trees are used to make an iterative algorithm for the inorder traversal of a tree. The idea is to point the null right child of any node to its inorder successor. There are two types of threaded binary trees.

a. Single-threaded:

Only the right null child of each node point towards the inorder successor of the tree.

b. Double-threaded:

Both the left and the right null child of each node point towards the inorder predecessor and inorder successor of the node respectively.

6. Expression Trees:

Expression tree is a special type of tree used to solve mathematical expressions. Each non-leaf node in an expression tree represents an operator and each leaf node is an operand.

 

Ending note:

In this blog, we discussed the Tree in data structures and Tree Transversal Algorithms used in Machine learning.

Special trees help to solve different problems in optimized time and space. Overall, trees are advantageous as they depict a structural correlation between the data. Moreover, trees also provide flexible insertion and sorting advantages.

Get one step closer to your dream job!

Prepare for your programming interview with Data Structures & Algorithms Interview Questions You’ll Most Likely Be Asked. This book has a whopping 200 technical interview questions on lists, queues, stacks, and algorithms and 77 behavioral interview questions crafted by industry experts and interviewers from various interview panels.