Shortest path in connecting all vertices

Given below 4 vertices on a two dimensional plane. Connect them in shortest possible way. In other words, there are 4 cities A, B, C and D at the corner of square of side (a) units. What will be the minimum cost of connecting these cities?

Those making circuit layouts of VLSI chips need to solve the puzzle smartly. Even 0.1% gain in space is huge on miniaturized chips.

Answer: Assuming the side of square as s, the minimum cost (road connecting all four cities) is s x (SQRT(3) + 1)

Splitting a binary search tree at a given node

22, Feb 2011
Given a node and root of tree, how to split the binary search tree into two different trees.

The idea is to walk down the tree till the node, and keep track of the path. Climb up the tree and separate the nodes into two different trees. The algorithm is simple.

split(z, T)
   x = z.left
   y = z.right


   splitter = z


   while(z.p is valid)
     if(z.p.left = z) // z is on left of its parent
        z = z.p
        z.left = y
        y.p = z
        y = z
     else             // z is on right of its parent
        z = z.p
        z.right = x
        x.p = z
        x = z


   // add splitter if required or delete it
   insert(splitter,x)


   x.p = nil
   y.p = nil


   return x and y as two split trees.

Understanding the algorithm will be simple, if we can draw a tree and its walking as per above pseudo code.

Combining (merge) two binary search trees

20th, February 2011

Given two binary search trees, how to combine them?

Note that the binary search tree has a property that every left subtree element will be less than or equal to the root element, and every right subtree element is greater than or equal to the root element.

Based on the property, let us assume that given trees T₁ and T₂, such that every element in T₁ <= every element in T₂. It will be easy to merge these two trees.

We need to figure out the root of merged tree. The root element can be either right extreme node in T₁ or left extreme node in T₂ to maintain BST property. So, the approach is to remove either of these nodes, make it as root, and attach T₁ as left subtree, T₂ as right subtree.

Find K-th smallest element in a binary search tree (BST)

11, Feb 2011


The question related to order statistics. A BST (non-linear data structure) represents data in an order fashion that satisfies the binary search tree property of "left node key should be <= root and right node key should be >= root".
Since we need K-th smallest element, we need to maintain # of elements in either of the sub-trees. By maintaining the count we can get the sub tree nodes in O(1) time complexity.


Assume the root has n nodes in its left subtree. If n <= K, we will continue search (recursion) for the smallest element in the left subtree. If K = n + 1, the root has the K-th smallest element. If k > n + 1, then we continue search the right subtree for the (K - n- 1)-th smallest element.


There are other approaches, like inorder traversal by maintaining the count, and stop search at K-th element or trivial case of  no K-th node.


I have published two approaches for finding k-th smallest element in BST (See the link).

QtWebkit - CRASH() macro

I have come across interesting code snippet in QtWebkit code base.


#define CRASH() do { \
    *(int *)(uintptr_t)0xbbadbeef = 0; \
    ((void(*)())0)(); /* More reliable, but doesn't say BBADBEEF */ \
} while(false)

The line,

((void(*)())0)();

caught my attention. Can you guess what is it doing? Pretty simple,

0 being casted to some type and is 'pointer type. It is of type "pointer to function taking nothing and returning nothing", and the function invoked. Ideally the code invoking function located address 0. I interpret it as power OFF simulation. Isn't it?

It is published on GeeksforGeeks.