My software development journey
Given a sorted array, how do we create binary search which height balanced. For example the array [1,2,3,4,5] must be transformed to the following binary tree 3 / 2 4 / 1 5 We can use the divide and conquer approach to solve this problem. To create a…
Given a binary search tree, how do we find a kth smallest or kth largest element? For example, given the following binary search tree. Third largest element is 6 Second smallest element is 2 Fifth largest element is 5 and so on… Solution: We can solve this problem by modifying the the in-order traversal method…
Given a binary search tree, how do we find the maximum and minimum elements in it? For example in the given tree, the maximum element is 8 and the minimum element is 1. This algorithm is based on the following simple observation. In a Binary search tree, the minimum element always lies on the left…
Given a binary tree how to find the height of the tree. It is defined as the number of nodes in the longest path from root to any leaf. We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the…
A binary search tree is a hierarchical data structure which stores data in a non-linear fashion. It supports the insertion, search and deletion operations in O( log n ) time. Take a look at the below picture. This is an example of binary search tree. The node at the top containing 5 is the root…
Given a Binary Search Tree (BST), How do we find the Lowest Common Ancestor (LCA) of the given two nodes? For example in the following BST, the LCA of 5 and 8 is 7 because it is the nearest ancestor common to both the nodes. Let us assume that the LCA(5,7) is 7 itself (…