You must have studied Arrays, Strings, Linked-Lists, and other Linear Data Structures up to this point. As you may be aware, the data is organised in a sequential manner,
and they adhere to some sort of data organisation order. However, when we progress to non-linear data structures, things will alter. The data in these non-linear data structures
is not organised in any type of sequence and is distributed randomly throughout the data structure. The non-linear data structures are multi-level, whereas the linear data
structures are only one level.
The binary tree, which is a special sort of tree data structure, is the first non-linear data structure we'll discuss. Enough with the introduction, let's get right to the point about why you've come.
A binary tree is defined as a tree with no more than two offspring.
Because each binary tree element can only have two offspring, we call them the left and right child. It has following parts
Left child Pointer
Right child Pointer
• Full Binary Tree: It's a specific type of binary tree that contains
either zero or two children. It means that every binary tree node should have two children, or that the parent node should be the leaf node or the external node itself.
• Complete Binary Tree: A complete binary tree is another sort of binary tree in which all of the tree levels, except the lowest, are completely filled with nodes. Furthermore, the last or lowest level of the binary tree should have every node on the left side.
• Perfect Binary Tree: If all internal nodes have exactly two children and every external or leaf node is at the same level or depth within the tree, it is said to be 'perfect.' 2h – 1 node in a perfect binary tree of height 'h'
• Balanced Binary Tree: A tree is considered to be balanced if its height is O(logN), where N is the number of nodes. In a balanced binary tree, the height of each node's left and right subtrees should differ by no more than one. A data structure like an AVL Tree or a Red-Black Tree can be used to create a balanced binary search tree.
• Degenerate Binary Tree: If every internal node has only one child, the binary tree is considered to be degenerate binary tree or pathological binary tree. In terms of performance, such trees are similar to linked lists.
A binary tree's search method is faster than that of other trees.
Only two traversals are required to sort the elements. It is simple to select the maximum and minimum elements.
Binary trees are also used in graph traversal.
Various postfix and prefix expressions can be converted using binary trees.
The maximum number of nodes in a binary tree at level 'n' is 2n.
In a binary tree of height 'h,' the maximum number of nodes is 2h – 1.
The number of leaf nodes in a binary tree with 0 or 2 children is always one more than the number of nodes with two children.
The minimum feasible height or number of layers in a Binary Tree with N nodes is Log2(N+1).
There are at least | Log2L |+ 1 levels in a Binary Tree with L leaves.
Traversal is a method of visiting every node in a tree and publishing their values. Because all nodes are connected by edges, we always start with the root (head) node (links).
That is, a node in a tree cannot be accessed at random. We can navigate a tree in three different ways.
Inorder Traversal: The Left Root Right policy is followed by an inorder traversal strategy. Left Root Right denotes that the root node's left subtree is explored first, followed by the root node, and finally the right subtree of the root node. The name inorder suggests that the root node is situated between the left and right subtrees.
1. To explore the left subtree, call Inorder (left-subtree)
2. Go to the source.
3. Call Inorder to traverse the correct subtree (right-subtree)
In preorder traversal, the root node is always traversed first, whereas in postorder traversal, it is traversed last. Preorder traversal is used to find a tree's prefix expression.
1. Go to the source.
2. Call Preorder from the left subtree (left-subtree)
3. Navigate to the appropriate subtree, i.e., call Preorder (right-subtree)
Postorder Traversal: One of the traversing techniques used to visit the node in the tree is postorder traversal. The LRN concept supports it (Left-right-node). Postorder traversal
is used to find a tree's postfix expression.
1. To explore the left subtree, use Postorder (left-subtree)
2. Call Postorder from the appropriate subtree (right-subtree)
3. Go to the source.
The obvious technique to traverse a tree without recursion is to use Stack. The algorithm for traversing a binary tree using stack is shown below. See this for the algorithm's step-by-step execution.
1. Make an empty stack called St.
2. Start with current node as root
3. push the current node to St and set current = current->left until current is NULL.
4. If current is NULL and the stack isn't empty, a) Remove the top item from the stack.
b) Set current = popped item->right to print the popped item.
c) Continue to step 3
5. We're done if current is NULL and stack is empty.
The above solutions have an O(n) time complexity, where n is the total number of nodes in the binary tree. The program's space complexity is O(n), because the space required is proportional to the tree's height.
Because a tree is not a linear data structure and nodes might have multiple child nodes, there may be numerous nodes to visit after a node has been visited. Nodes that need to be visited later must be saved in some way for future visits.
This can be accomplished by either saving the nodes in a stack for future visits or by utilising recursion, in which the nodes are implicitly saved in a stack for future visits. It's about using Morris Traversal to achieve inorder tree traversal without requiring recursion or stack.
Morris Traversal is based on the Threaded Binary Tree concept. We build links to Inorder successors and display the data using these links in this traversal, then undo the changes to restore the original tree.
Steps involve in Morris Traversal
1. Create in-order successor linkages
2. Using the formed links, print the information (the tree is altered during the traversal)
3. Revert the changes and restore the original tree after the traversal is complete.
1. Set the root to be the current node curr.
2. Check if curr has a left child when it is not NULL.
3. If curr has no left child, print curr and update it to point to the node to curr's right.
4. Otherwise, make curr the right child of curr's left subtree's rightmost node.
5. Curr should be updated to this left node.
The following are some of the benefits of employing the Morris Traversal method for inorder tree traversal:
Allows traversal of inorder trees without recursion or stacking.
Unlike when a stack is utilised for the purpose, it does not require additional space.
Recursion requires more memory and time than this method.
The parent is tracked by the node.
The Morris Traversal method for inorder tree traversal has the following drawbacks:
This results in a more complicated tree.
At any given time, only one traversal is possible.
When both children are missing from a binary tree and both node values point to their ancestors, it can be error-prone.
A tree is said to be balanced when all three conditions are met:
The difference in height between the left and right subtrees is only one.
The left-hand subtree is well-balanced.
The balanced right subtree
A node in a tree is height-balanced if the heights of its subtrees differ by no more than one.
A tree is considered to be height-balanced if all of its nodes are of equal height.
A balanced BST has a height of log n, where n is the number of elements in the tree. In the worst situation and in an imbalanced BST, the tree's height can reach n, making it identical to a linked list. In the worst scenario, each operation (search, insertion, and deletion) requires time O(n), which can be avoided.
|BINARY TREE||BINARY SEARCH TREE|
|A BINARY TREE is a non-linear data structure in which each node can only have two children.||A node-based binary tree with right and left subtrees that are also binary search trees is known as a BINARY SEARCH TREE.|
|Because the BINARY TREE is unordered, it takes longer to insert, delete, and search.||Because of the ordered properties, insertion, deletion, and searching of an element is faster in BINARY SEARCH TREE than in BINARY TREE.|
|There is no ordering in a binary tree in terms of how the nodes are placed.||The elements in the left subtree are less than the nodes element, while the ones in the right subtree are greater.|
Two binary trees are similar if they have the same data and organisation. This can be performed by visiting both trees and comparing their data and arrangements.
The algorithm that will enable us to do so is as follows:
Examine the data of the root node (t1 data ==t2 data).
Check the left subtree recursively. sameTree(t1->left subtree, t2->left subtree)
Similarly, we look for the correct right subtree.
If the conditions outlined above are met, we will issue a 1
A binary search tree (BST) is a binary tree with a key for each internal node. A binary search tree's rule is as follows:
A key can be bigger than all the keys in a node's left subtree.
The right subtree of a node can have a key that is smaller than the subtree's other keys.
If n1 has the key 5, then every node in n1's left subtree has keys less than 5 and every node in n1's right subtree has keys greater than 5.
A tree's diameter is the length of the longest path between any two nodes. The number of edges that go along a path determines its length. Remember that this node does not have to pass via the tree's root node.
When a dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a breadthward motion and uses a queue to remember to retrieve the next vertex to start a search.
Step 1: Go to the next unexplored vertex. It should be marked as visited. Show it off. Add it to a queue.
Step 2: Remove the first vertex from the queue if no neighbouring vertex is discovered.
Step 3: Repetition of Rules 1 and 2 until the line is empty.
DFS (depth–first search) is a tree or graph data structure traversal or search algorithm. Starting at the base (choosing any arbitrary node as the graph's root), one explores as far as possible along each branch before returning to the beginning.
A tree is an undirected graph with precisely one path connecting any two vertices. In other words, a tree is any acyclic connected graph. We have the following tree traversal methods:
Visit each node first, then its children.
Visit each node after its children, in reverse order.
Visit the left subtree, node, and right subtree in this order (for binary trees only).
The Delete function is used to remove a node from a binary search tree. However, we must delete a node from a binary search tree without breaking the property of the binary search tree. A node can be deleted from a binary search tree in three different ways.
Leaf node deletion:
This is the simplest example, simply replace the leaf node with NULL and free the allotted space.
One child node deletion
Replace the node with its child in this case, then remove the child node, which now has the value to be destroyed. Simply replace it with NULL and the allotted space will be free.
Two child node deletion
In comparison to the other two situations, this one is a little more complicated. The node that is to be destroyed, on the other hand, is recursively replaced with its in-order successor or predecessor until the node value (to be removed) is placed on the tree's leaf. Replace the node with NULL and clear the allocated space after the process.
A binary tree's lowest common ancestor (LCA) is the lowest (i.e., deepest) node that has both x and y as descendants, where each node might be a descendant of itself (so if x is reachable from w, w is the LCA). In other words, the LCA of x and y is their shared ancestor that is the furthest away from the root.
In the binary tree, we can recursively locate the lowest common ancestor of nodes x and y. The trick is to locate the node in a binary tree that has one key in the left subtree and the other in the right subtree. If y is in the subtree rooted at node x, then x is the LCA; otherwise, if x is in the subtree rooted at node y, then y is the LCA.
If both the left and right child nodes of a node are NULL, it is considered a leaf node.
1) Return 0 if the node is NULL.
2) Otherwise, return 1 if the left and right child nodes are both NULL.
3) If not, recursively calculate the tree's leaf count using the algorithm below.
Leaf count of a tree = left subtree leaf count + right subtree leaf count
The rule that the left subtree should have lower key values and the right subtree should have higher key values distinguishes a binary tree from a binary search tree.
The following traversal approaches can be used to achieve this:
Make a temporary array to hold the inorder traverse of the tree.
Sorting the temporary array is required. Any sorting method can be used in this situation.
Once more, traverse the tree in reverse order.
Copy the array elements to each tree node one by one.
The highest number of edges in a path from a leaf node to a target node is the height of a node in a binary tree. If there are no additional nodes connected to the target node, the height of that node will be 0. A binary tree's height is equal to the height of the root node in the entire binary tree. In other words, the highest number of edges from the root to the farthest leaf node determines the height of a binary tree.
This page has reached the end of its content. You should be able to construct your own programmes with the material on this page and some practise, and little projects are highly encouraged for improving your programming skills. You won't be able to learn everything you need to know about programming in a single course it's like a marathon.