Trees

Question: Given the root pointer to a binary tree, find the maximum element present in it. Input: Sample Tree (Pointer to node 1 is given) Output: Maximum = 9 We discussed how to find the maximum element in a binary tree using recursion in this post. Find maximum element in a binary tree That involved recursion. If recursion seems difficult to you, we can even solve this problem with the help of level order traversal of binary tree. The property of level order traversal is that it passes through each…

Question: Given the root pointer to a binary tree, find the maximum element present in it. Input: Sample Tree (Pointer to node 1 is given) Output: Maximum = 9 One simple way of solving this problem is to find the maximum element in the left sub-tree, find maximum in the right sub-tree, compare it with the root data and select the one that gives the maximum value. This approach can be easily implemented with recursion. This approach works because each node of the tree has 3 parts -> the root,…

We discussed the basic tree traversals in this post – Basic tree traversals We learned about the pre-order traversal, in-order traversal and post-order traversal. These are standard traversals that are related with root, left sub-tree and the right sub-tree. Level order traversal follows an entirely different approach and is not related with the left sub-tree and the right sub-tree. It does not hold the same property for all the nodes and hence recursive technique cannot be applied to level order traversal. Let us try to understand with the help of…

We discussed about the basic tree traversals in this post – Binary Tree Traversals Lets take our own sample tree for understanding post-order traversal. In Post-Order traversal, the root is visited after both sub-trees are completed. Post-order traversal is defined as follows:- Traverse the left sub-tree in post-order. (Step 1) Traverse the right sub-tree in post-order. (Step 2) Visit the root The post-order traversal can then be defined in this way – The nodes of the tree will therefore be in order – 4, 5, 2, 6, 7, 3, 1…

We discussed about the tree traversal techniques in this post- Binary Tree Traversals Please see pre-order traversal to understand the basics of visiting nodes. We have our same sample tree Now let us try to understand the In-order traversal. In in-order traversal, the root is traversed between the sub trees. In-order traversal is defined as follows. Traverse the left sub-tree Visit the node Traverse the right sub-tree So when we apply the in-order traversal on our example tree this will be done as:- We get the final in-order traversal as:-…

We learned about the different type of traversals in this post Binary Tree Traversals In pre-order traversal, each node is processed before (pre) either of its sub-trees. This is the simplest traversal to understand. However, even though each node is processed before the sub-trees, it still requires that some information must be maintained while moving down the tree. Let us consider an example In the example tree shown above, the node “1” is processed first, then the left sub-tree, followed by the right sub-tree. Therefore, processing must return to the…

We have covered some basics about the tree in the previous posts- The TREE data structure Binary Trees Structure of Binary Trees Now let us try to see, how we can traverse a tree. In order to process trees, we need a mechanism for traversing them and that forms the subject of this post. The process of visiting all nodes of a tree is called tree traversal. Each of the nodes is processed only once but they maybe visited more than once. As we have already seen that in linear…

We learned about trees and binary trees in the following posts:- The tree data structure The basics of Binary Tree Now let us try to define the structure of the binary tree. For simplicity, assume that the data of the nodes are integers. One way to represent a node (which contains the data) is to have two links which points to the left and right children along with data fields as shown below: Please note that in trees, the default flow is from parent to children and showing directed branches…

A tree is called a binary tree if each node has zero child, one child or two children. Empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a root and two disjoint binary trees, called the left and right sub-trees of the root. Generic Binary Tree Types of Binary Trees Strict Binary Tree: A tree is called a strict binary tree if each node has exactly two children or no children. Full Binary Tree: A binary tree is called a full binary…

A tree is a data structure similar to a linked list but instead of each node simply pointing to the next node in a linear fashion, each node points to a number of nodes. Tree is an example of a non-linear data structure. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. In trees ADT (Abstract Data Type), order of the elements is not important. If we need ordering information, linear data structures like linked lists, stacks, queues etc can be…