binary trees

PostOrder Node Iterator of Binary Tree

Introduction This is going to be a short post. The problem statement at hand is to write PostOrder Node Iterator of Binary Tree. For those who do not know the Iterator Design Pattern or Post Order Successor, check the next section. Iterator Design Pattern This pattern is used to iterate through a collection or group. The Java Iterator supports the following three methods : hasNext() : returns a boolean true if the collection has elements after the last returned element, false otherwise. next() : returns the next element in the collection. remove() : removes the element from the coll...
Read More

Binary Tree Linking Neighbors

Introduction Problem Statement : Given a regular binary tree with left, right and peer node pointers. The left and the right pointers are already populated. We need to make the peer pointer point to the next right neighbor on the same level. Understanding the problem Here is a diagram to explain what is needed. The red peer pointer points to the immediate right neighbor if the neighbor exists. Approach 1 The first solution which comes in mind is to do a custom, level order traversal as done in the post. And, in each iteration of the inner loop, just link each of the node to the next in ...
Read More

Tree Diameter

Introduction This is the fifth article in the Tree Traversals - Online Classes. A very interesting problem is to find the diameter of a tree. The challenge is not in coding the algorithm but in understanding the meaning of the problem. We will try to define the problem so that visualizing the solution becomes easy. Defining the problem - Tree Diameter Few confusions about the diameter must be avoided before we start. The tree diameter is always the distance between two leaf nodes The diameter may or may not pass through the root. The diameter can also lie on one of the two sides,...
Read More

Level Order Tree Traversal

Introduction This is the third article in the Tree Traversals - Online Classes. I have written many articles about non-linear data structures and their traversals. But the more you dive in you can find many more ways to traverse a tree. Here we try to solve the level order tree traversal for a binary tree and we will also try to figure out other variations of this traversal. This can we precisely extended for a n-ary tree as well. Defining the problem Let us consider the above tree, if we follow the blue line from root till end and print all the nodes, we will end up printing the lev...
Read More

Count Binary Search Trees created from N unique elements

[nextpage title="Introduction"] This is the third article for Binary Search Trees, to read more about the previous article, please check the topic Binary Search Tree Basics – a detailed discussion. To get updates on the coming articles in the series, please use the Subscribe feature on the right panel. Purpose of article This article explains few more aspects of binary search tree (BST). In the last article we learnt to construct a BST and then we revisited our technique to construct a better BST with the same. So this means that there can be more than one BST possible with a given set of e...
Read More