Trees�

By

Mr. Abhijit T. Somnathe

What is Tree?

• A tree is a hierarchical data structure defined as a collection of nodes.
• Nodes represent value and nodes are connected by edges.
• This hierarchical structure of trees is used in Computer science as an abstract data type for various applications like data storage, search and sort algorithms.

​

What is Tree?

• Suppose we want to show the employees and their positions in the hierarchical form then it can be represented as shown below.

​

What is Tree?

• Let's understand some key points of the Tree data structure.
• A tree data structure is defined as a collection of objects or entities known as nodes that are linked together to represent or simulate hierarchy.
• A tree data structure is a non-linear data structure because it does not store in a sequential manner. It is a hierarchical structure as elements in a Tree are arranged in multiple levels.

What is Tree?

• In the Tree data structure, the topmost node is known as a root node.
• Each node contains some data, and data can be of any type.
• In the above tree structure, the node contains the name of the employee, so the type of data would be a string.
• Each node contains some data and the link or reference of other nodes that can be called children.

Tree

Tree Terminology

• In the above structure, each node is labeled with some number. Each arrow shown in the above figure is known as a link between the two nodes.
• Root: The root node is the topmost node in the tree hierarchy. In other words, the root node is the one that doesn't have any parent. In the above structure, node numbered 1 is the root node of the tree. If a node is directly linked to some other node, it would be called a parent-child relationship.

Tree Terminology

• Child node: If the node is a descendant of any node, then the node is known as a child node.
• Parent: If the node contains any sub-node, then that node is said to be the parent of that sub-node.
• Sibling: The nodes that have the same parent are known as siblings.

Tree Terminology

• Leaf Node: The node of the tree, which doesn't have any child node, is called a leaf node. A leaf node is the bottom-most node of the tree. There can be any number of leaf nodes present in a general tree. Leaf nodes can also be called external nodes.
• Internal nodes: A node has atleast one child node known as an internal.

Tree Terminology

• Ancestor node: An ancestor of a node is any predecessor node on a path from the root to that node. The root node doesn't have any ancestors. In the tree shown in the above image, nodes 1, 2, and 5 are the ancestors of node 10.
• Descendant: The immediate successor of the given node is known as a descendant of a node. In the above figure, 10 is the descendant of node 5.

Properties of Tree Data Structure

Properties of Tree Data Structure

• Recursive data structure: A tree can be defined as recursively because the distinguished node in a tree data structure is known as a root node. The root node of the tree contains a link to all the roots of its subtrees. In figure, the left subtree is shown in the yellow color, and the right subtree is shown in the red color. The left subtree can be further split into subtrees shown in three different colors. Recursion means reducing something in a self-similar manner. So, this recursive property of the tree data structure is implemented in various applications.

Properties of Tree Data Structure

• Number of edges: If there are n nodes, then there would n-1 edges. Each arrow in the structure represents the link or path. Each node, except the root node, will have atleast one incoming link known as an edge. There would be one link for the parent-child relationship.

Properties of Tree Data Structure

• Depth of node x: The depth of node x can be defined as the length of the path from the root to the node x. One edge contributes one-unit length in the path. So, the depth of node x can also be defined as the number of edges between the root node and the node x. The root node has 0 depth.
• Height of node x: The height of node x can be defined as the longest path from the node x to the leaf node.

Types of Tree

• Below are the types of trees in a data structure:

1. General Tree

2. Binary Tree

3. Binary Search Tree

4. AVL Tree

5. Red-Black Tree

6. N-ary Tree

General Tree

• If no constraint is placed on the tree’s hierarchy, a tree is called a general tree. Every node may have as many number of children in General Tree. The tree is the super-set of all other trees.

​

Binary Tree

Binary Tree

• The binary tree is the kind of tree in which most two children can be found for each parent.
• The kids are known as the left kid and right kid. Binary tree are more popular than most other trees.
• When certain constraints and characteristics are applied in a Binary tree, a number of others such as AVL tree, BST (Binary Search Tree), RBT tree, etc. are also used.

Binary Search Tree

Binary Search Tree

• Binary Search Tree (BST) is a binary tree extension with several optional restrictions.
• The left child value of a node should in BST be less than or equal to the parent value, and the right child value should always be greater than or equal to the parent’s value.
• This Binary Search Tree property makes it ideal for search operations since we can accurately determine at each node whether the value is in the left or right sub-tree. This is why the Search Tree is named.

AVL Tree

• AVL tree is a binary search tree self-balancing.
• On behalf of the inventors Adelson-Velshi and Landis, the name AVL is given.
• This was the first tree that balanced dynamically.
• A balancing factor is allocated for each node in the AVL tree, based on whether the tree is balanced or not.
• The height of the node kids is at most 1.

AVL Tree

AVL Tree

• In the AVL tree, the correct balance factor is 1, 0 and -1.
• If the tree has a new node, it will be rotated to ensure that it is balanced. It will then be rotated.
• Common operations such as viewing, insertion, and removal take O(log n) time in the AVL tree.
• It is mostly applied when working with Lookups operations.

Red-Black Tree

• Another kind of auto-balancing tree is red-black.
• According to the red-black tree’s properties, the red-black name is given because the Red-black tree has either red or Black painted on each node.
• It maintains the balance of the forest.

Red-Black Tree

Red-Black Tree

• Even though this tree is not fully balanced, the searching operation only takes O (log n) time.
• When the new nodes are added in Red-Black Tree, nodes will be rotated to maintain the Red-Black Tree’s properties.

N-ary Tree

N-ary Tree

• The N-ary tree is a tree that allows us to have N number of children of a particular node, hence the name N-ary, making it slightly complex than the very common binary trees that allow us to have at most 2 children of a particular node.
• A complete N-ary tree is a tree where kids of a node either are 0 or N.

​

Binary Tree Representation

• A binary tree data structure is represented using two methods as follows.
• Array Representation
• Linked List Representation

​

• Consider the following binary tree.

Binary Tree Representation

Array Representation of Binary Tree

• In array representation of a binary tree, we use one-dimensional array (1-D Array) to represent a binary tree.
• Consider the above example of a binary tree and it is represented as follows.

​

Array Representation of Binary Tree

• To represent a binary tree of depth 'n' using array representation, we need one dimensional array with a maximum size of 2n + 1.

Linked List Representation of Binary Tree

• We use a double linked list to represent a binary tree.
• In a double linked list, every node consists of three fields. First field for storing left child address, second for storing actual data and third for storing right child address.

Linked List Representation of Binary Tree

• In this linked list representation, a node has the following structure.

​

​

​

​

• The above example of the binary tree represented using Linked list representation is shown as follows.

​

​

​

Linked List Representation of Binary Tree

Binary Tree Traversals

• Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.
• When we wanted to display a binary tree, we need to follow some order in which all the nodes of that binary tree must be displayed.
• In any binary tree, displaying order of nodes depends on the traversal method.

Binary Tree Traversals

• There are three types of binary tree traversals.
• In - Order Traversal
• Pre - Order Traversal
• Post - Order Traversal

​

• Consider the following binary tree.

Binary Tree Traversals

In - Order Traversal (Left Child - Root – Right Child)

• In In-Order traversal, the root node is visited between the left child and right child.
• In this traversal, the left child node is visited first, then the root node is visited and later we go for visiting the right child node.
• This in-order traversal is applicable for every root node of all subtrees in the tree.

In - Order Traversal (Left Child - Root – Right Child)

• This is performed recursively for all nodes in the tree.

​

​

​

​

​

• That means here we have visited in the order of I - D - J - B - F - A - G - K - C - H using In-Order Traversal.

Pre - Order Traversal (Root - Left Child – Right Child)

• In Pre-Order traversal, the root node is visited before the left child and right child nodes.
• In this traversal, the root node is visited first, then its left child and later its right child.
• This pre-order traversal is applicable for every root node of all subtrees in the tree.

Pre - Order Traversal (Root - Left Child – Right Child)

​

​

​

​

​

​

• That means here we have visited in the order of A-B-D-I-J-F-C-G-K-H using Pre-Order Traversal.

Post - Order Traversal (Left Child - Right Child - Root)

• In Post-Order traversal, the root node is visited after left child and right child.
• In this traversal, left child node is visited first, then its right child and then its root node.
• This is recursively performed until the right most node is visited.

​

​

​

​

Post - Order Traversal (Left Child - Right Child - Root)

​

​

​

​

​

​

• Here we have visited in the order of I - J - D - F - B - K - G - H - C - A using Post-Order Traversal.

Basic operations on a Binary Search Tree

• Create: Creates an empty tree.
• Insert: Insert a node in the tree.
• Search: Searches for a node in the tree.
• Delete: Deletes a node from the tree.
• In-order: In-order traversal of the tree.
• Pre-order: Pre-order traversal of the tree.
• Post-order: Post-order traversal of the tree.

​

​

​

Basic operations on a Binary Search Tree

Predecessor of a node

• Predecessors can be described as the node that would come right before the node you are currently at. To find the predecessor of the current node, look at the right-most/largest leaf node in the left subtree.

Successor of a node

• Successors can be described as the node that would come right after the the current node. To find the successor of the current node, look at the left-most/smallest leaf node in the right subtree.

Basic operations on a Binary Search Tree

Create

• Initially an empty tree without any nodes is created. The variable/identifier which must point to the root node is initialized with a NULL value.

Basic operations on a Binary Search Tree

Search

• You always start searching the tree at the root node and go down from there.
• You compare the data in each node with the one you are looking for.
• If the compared node doesn't match then you either proceed to the right child or the left child, which depends on the outcome of the following comparison.

Basic operations on a Binary Search Tree

• If the node that you are searching for is lower than the one you were comparing it with, you proceed to the left child, otherwise (if it's larger) you go to the right child.
• Because the BST is structured, that the right child is always larger than the parent and the left child is always lesser.

Basic operations on a Binary Search Tree

Insert

• It is very similar to the search function.
• You again start at the root of the tree and go down recursively, searching for the right place to insert our new node.
• If a node with the same value is already in the tree, you can choose to either insert the duplicate or not.
• Some trees allow duplicates, some don't. It depends on the certain implementation.

Basic operations on a Binary Search Tree

Deletion

• There are 3 cases that can happen when you are trying to delete a node. If it has,

1. No subtree (no children): This one is the easiest one. You can simply just delete the node, without any additional actions required.

2. One subtree (one child): You have to make sure that after the node is deleted, its child is then connected to the deleted node's parent.

3. Two subtrees (two children): You have to find and replace the node you want to delete with its in-order successor (the leftmost node in the right subtree).

Expression Tree

• The expression tree is a binary tree in which each internal node corresponds to the operator and each leaf node corresponds to the operand.
• Here, In-order traversal of expression tree produces infix version of given postfix expression.

Expression Tree

• So for example expression tree for [3 + ((5+9)*2)] would be,

​

Construction of an Expression Tree

• Expression Tree is a special kind of binary tree with the following properties:

1. Each leaf is an operand. Examples: a, b, c, 6, 100

2. The root and internal nodes are operators. Examples: +, -, *, /, ^

3. Subtrees are subexpressions with the root being an operator.

Construction of an Expression Tree

• Let us consider a postfix expression is given as an input for constructing an expression tree. Following are the step to construct an expression tree:

1. Read one symbol at a time from the postfix expression.

2. Check if the symbol is an operand or operator.

Construction of an Expression Tree

3. If the symbol is an operand, create a one node tree and push a pointer onto a stack.

4. If the symbol is an operator, pop two pointers from the stack namely T1 & T2 and form a new tree with root as the operator, T1 & T2 as a left and right child.

5. A pointer to this new tree is pushed onto the stack.

Construction of an Expression Tree

• Thus, An expression is created or constructed by reading the symbols or numbers from the left. If operand, create a node. If operator, create a tree with operator as root and two pointers to left and right subtree

Construction of an Expression Tree

Postfix Expression Construction

• The input is: a b + c *
• The first two symbols are operands, we create one-node tree and push a pointer to them onto the stack.

​

Construction of an Expression Tree

• Next, read a'+' symbol, so two pointers to tree are popped,a new tree is formed and push a pointer to it onto the stack.

​

Construction of an Expression Tree

• Next, 'c' is read, we create one node tree and push a pointer to it onto the stack.

​

Construction of an Expression Tree

• Finally, the last symbol is read ' * ', we pop two tree pointers and form a new tree with a, ' * ' as root, and a pointer to the final tree remains on the stack.

​

​

Huffman Tree

• Huffman coding provides codes to characters such that the length of the code depends on the relative frequency or weight of the corresponding character.

​

Huffman Tree

• Huffman codes are of variable-length, and without any prefix (that means no code is a prefix of any other).
• Any prefix-free binary code can be displayed or visualized as a binary tree with the encoded characters stored at the leaves.
• Huffman tree or Huffman coding tree defines as a full binary tree in which each leaf of the tree corresponds to a letter in the given alphabet.

Huffman Tree

• The Huffman tree is treated as the binary tree associated with minimum external path weight that means, the one associated with the minimum sum of weighted path lengths for the given set of leaves.
• So the goal is to construct a tree with the minimum external path weight.

Huffman Tree

• An example is given below-

Letter Frequency Table

​

​

​

​

Huffman Tree

• The Huffman tree (for the above example) is given below –

​

​

​

​

Huffman Tree

Huffman Code

​

​

​

​

ANY DOUBTS?