Determine if tree is AVL in O(n)

The following java method will determine if a binary tree is AVL (and, obviously BST)

Determine max and min root leaf path in a Binary Search Tree (BST)

Let’s view an algorithm that manage to find the minimum and the maximum root-leaf path in a binary search tree. I used three stacks in this algorithm, one is temporary and the other will be filled with the results. Note that if we change: i > maxSeq.size() with i >= maxSeq.size() we get the longest …

Determine max and min root leaf path in a Binary Search Tree (BST) Read More »

Quickselect algorithm

Suppose we want to know the k-th element of the array, how we would do? We would sort the array, with O(nlogn) for example Then we will get the element searched But there’s a faster method using a similar idea of QuickSort. Let’s view the QuickSelect algorithm in pseudocode applied to the problem of find the …

Quickselect algorithm Read More »