Bytes Jar

In the continuation of Binary Search Tree articles here comes another exciting one. In this article we will see how we can find the nth smallest element in a Binary Search Tree. Let's take the example of binary search tree given in the figure below (Fig 1.0) and see how to find its 3rd smallest element. Fig 1.0 Explanation - One thing we know for sure that we will have to traverse through this tree if we want to find any element, if so then what could be better than In-Order Traversal in this case because it gives us the nodes in ascending order. Now once we know how to traverse in ascending order only thing left is to take a counter to check whether we have traversed the n (3 in this example) nodes. Once the counter reach the value n we know its our nth smallest element. We will use the similar approach in the implementation give below, we will traverse the tree using In-Order traversal and take a counter to check the number of nodes we have traversed and as soon as the counter...

Height of a Binary tree is the length of the path form its root node to its farthest leaf node or we can say the longest path from root node to any of the leaf node (here path means the link between two nodes). For example - height of the binary tree in the figure given below (Fig 1.0) is 3. As we can see that this tree has two leaf nodes 3 and 12 but node leaf 3 is the farthest from the root and length of the path between 10 (root node) and 3 (farthest leaf node) is 3 hence height of the tree is 3. From above example comes our algorithm to calculate the height of the tree, we will calculate the height of the left and right subtree of each node recursively and consider the height of the tree including the root node - adding one to the greater of the two heights (left and right subtree heights). Fig 1.0 Implementation - In below code we have implementaed a custom BST with a public method getHeight() which internaly calls another private method getHeight() passing root of the tree ...

A height balanced search tree is the one in which the difference of height of the left subtree and height of the right subtree is not more than one for each node. Height of a tree node -  Length of the longest path from the node to the leaf node. The height of a tree is the height of its root node and the height of a leaf node is 0. Check this article -  Calculate the height of a binary tree Now before creating a height balanced search tree let's understand why do we need a height balanced BST ?     We know that a Binary Search Tree (BST) is a binary tree in which for each node its left child node is less than the node and right child node is greater than the node itself. This property of the BST makes it suitable for search operations because while searching for a key during tree traversal, on each node we can eliminate the traversal of one entire subtree of the node (left subtree or right subtree) based on the value of search key. For example let's try searching th...

Inorder is one of the ways to traverse a binary tree in depth first fashion. We have already discussed Inorder Traversal (Left, Root, Right) of a binary thee in our previous articles using recursive approach and using stack (without recursion). But in this article we will discuss Morris Traversal which is used to traverse a Binary Tree without using recursion or Stack. If you are interested in Inorder traversal using recursion or iterative approach using Stack, refer below articles - Tree Traversal - Depth First (Iterative/ Non Recursive Approach) Tree Traversals - Depth First (Recursive Approach) Explanation Morris Traversal - Suppose we have a binary tree as shown in the figure below. Now we already know that Inorder traversal follows this order - Left, Root, Right. And this sequence must be followed by all the  sub trees  as well. In-order traversal of this Tree would be -  2 3 4 5 6 8 10 In this sequence we can clearly see that after visiting the left node or left sub...

 Binary search tree or BST is a hierarchical data structure which can be traversed in more than one ways. Preorder traversal is one of the way in which we can traverse a binary tree. In this article we will discuss how we can create a new Binary Search Tree if we are given an array of its keys generated by Preorder traversal (Root, Left, Right) of the tree. You can visit this link to understand the Preorder traversal along with other depth first traversal strategies of BST -  BST Depth First Traversal Strategies (Inorder, Preorder, Postorder) . We will use recursive approach for BST construction from preorder array. Explanation - Suppose we are given this preorder array - {10, 5, 1, 7, 40, 30, 50}. For better understanding refer the BST figure given below - We already know that in preordrer traversal the order is (Root, Left, Right) for each sub tree, the given array basically represents the overall tree so its very first node would be the root node of the tree obviously. ...

In this particular articular we will discuss the iterative or non recursive approach to traverse a binary tree. We can traverse through a binary tree using stack.  There are three ways in which a tree can be traversed using depth first approach. Inorder (Left, Root, Right) Preorder (Root, Left, Right) Postorder (Righ, Left, root) We have already discussed the details about all three approaches and traversal using recursive approach in our previous article -  Tree Traversals - Depth First (Recursive Approach) . We will implement the iterative approach using stack. Implementation -  package ds.tree; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class BStree { private Node root; public BStree(int rootData) { this.root = new Node(rootData); } static class Node { int data; Node left; Node right; public Node(int data) { this.data = data; } } public void insert(int data) { Node nNode = new Node(data); No...

In our previous article we have learned that being a hierarchical data structure binary tree can be traversed in more than one way. We have already covered the depth first traversal of the tree in the article here -  Tree Traversals - Depth First . In this article we will cover the Breadth First or Level Order traversal of a binary tree. Breadth First or level Order Traversal - In this approach we visit all the nodes of a tree at a particular level before moving to another level. We start the traversal starting from the root node and move downward in the tree visiting all the nodes of the level until we finish the last level of the tree. For example lets assume we have a binary tree with structure as shown in the figure below - Now if we print the nodes of this tree using the level order traversal we will get the keys in this sequence - 5 3 8 2 4 6 10 Level order traversal implementation - package ds.tree; import java.util.LinkedList; import java.util.Queue; public clas...

Tree is a hierarchical data structure and  therefore can be traversed in more than one way unlike liner data structures. Each order of traversal has its own benefits. Generally there are two main ways to traverse a binary tree - 1. Depth First Traversal 2. Breadth First Traversal In this particular article we will discuss three ways to traverse a binary tree using Depth First approach. Also we can implement the traversal using either recursive approach or Iterative approach, but here we will go with recursive approach. For Breadth First or level order Traversal visit this link - Binary Tree - Breadth First or Level Order Traversal In Depth First traversal there are 3 ways to traverse a binary tree - Inorder Traversal (Left, Root, Right) Preorder Traversal (Root, Left, Right) Postorder Traversal (Left, Right, Root) 1. Inorder Traversal - For Inorder Traversal following sequence is followed - - Visit the left subtree. - Visit root Node - Visit right subtree Basically for ea...

In this article we will see how we can write the insert method for a binary tree using recursive approach. We have already covered the iterative approach in this article -  Binary Search Tree Insertion Iterative Approach  with some basic details about binary search tree data structure. package ds.tree; public class BStree { private Node root; public BStree(int rootData) { this.root = new Node(rootData); } static class Node { int data; Node left; Node right; public Node(int data) { this.data = data; } } public void insertRecursive(int data) { insertRec(this.root, data); } private Node insertRec(Node root, int data) { if(root == null) return new Node(data); if(root.data &lt data) root.right = insertRec(root.right, data); else root.left = insertRec(root.left, data); return root; } public void printTree() { System.out.print(root.data + ", " + root.left.data + ", " + root.right.data); } } Notice that ...

This article concerns with writing the insert method for inserting a value in a binary search tree datastructure using iterative approach. Before continuing further you must have some basic knowledge about binary search tree data stucture. Basically binary search tree is a hierarchical data structure in which each node has at most two child nodes (left node and righ node).  In binary search tree left and right nodes are arranged in such a way that for each node its left node contains key less than the node and right node contains the key greater than the node. Now without going into much details about the binary tree lets start writing the code for a binary tree. package ds.tree; public class BStree { private Node root; public BStree(int rootData) { this.root = new Node(rootData); } static class Node { int data; Node left; Node right; public Node(int data) { this.data = data; } } public void insert(int data) { Node nNode = new Node(data); Node r...