Create Balanced Binary Search Tree from Sorted lin

Question

What's the best way to create a balanced binary search tree from a sorted singly linked list?

Answer 1

If you know how many nodes are in the linked list, you can do it like this:

// Gives path to subtree being built.  If branch[N] is false, branch
// less from the node at depth N, if true branch greater.
bool branch[max depth];

// If rem[N] is true, then for the current subtree at depth N, it's
// greater subtree has one more node than it's less subtree.
bool rem[max depth];

// Depth of root node of current subtree.
unsigned depth = 0;

// Number of nodes in current subtree.
unsigned num_sub = Number of nodes in linked list;

// The algorithm relies on a stack of nodes whose less subtree has
// been built, but whose right subtree has not yet been built.  The
// stack is implemented as linked list.  The nodes are linked
// together by having the "greater" handle of a node set to the
// next node in the list.  "less_parent" is the handle of the first
// node in the list.
Node *less_parent = nullptr;

// h is root of current subtree, child is one of its children.
Node *h, *child;

Node *p = head of the sorted linked list of nodes;

LOOP // loop unconditionally

    LOOP WHILE (num_sub > 2)
        // Subtract one for root of subtree.
        num_sub = num_sub - 1;

        rem[depth] = !!(num_sub & 1); // true if num_sub is an odd number
        branch[depth] = false;
        depth = depth + 1;
        num_sub = num_sub / 2;
    END LOOP

    IF (num_sub == 2)
        // Build a subtree with two nodes, slanting to greater.
        // I arbitrarily chose to always have the extra node in the
        // greater subtree when there is an odd number of nodes to
        // split between the two subtrees.

        h = p;
        p = the node after p in the linked list;
        child = p;
        p = the node after p in the linked list;
        make h and p into a two-element AVL tree;
    ELSE  // num_sub == 1

        // Build a subtree with one node.

        h = p;
        p = the next node in the linked list;
        make h into a leaf node;
    END IF

    LOOP WHILE (depth > 0)
        depth = depth - 1;
        IF (not branch[depth])
            // We've completed a less subtree, exit while loop.
            EXIT LOOP;
        END IF

        // We've completed a greater subtree, so attach it to
        // its parent (that is less than it).  We pop the parent
        // off the stack of less parents.
        child = h;
        h = less_parent;
        less_parent = h->greater_child;
        h->greater_child = child;
        num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1;
        IF (num_sub & (num_sub - 1))
          // num_sub is not a power of 2
          h->balance_factor = 0;
        ELSE
          // num_sub is a power of 2
          h->balance_factor = 1;
        END IF
    END LOOP

    IF (num_sub == number of node in original linked list)
        // We've completed the full tree, exit outer unconditional loop
        EXIT LOOP;
    END IF

    // The subtree we've completed is the less subtree of the
    // next node in the sequence.

    child = h;
    h = p;
    p = the next node in the linked list;
    h->less_child = child;

    // Put h onto the stack of less parents.
    h->greater_child = less_parent;
    less_parent = h;

    // Proceed to creating greater than subtree of h.
    branch[depth] = true;
    num_sub = num_sub + rem[depth];
    depth = depth + 1;

END LOOP

// h now points to the root of the completed AVL tree.

For an encoding of this in C++, see the build member function (currently at line 361) in https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/avl_tree.h . It's actually more general, a template using any forward iterator rather than specifically a linked list.

Answer 2

Hope the detailed explanation on this post helps: http://preparefortechinterview.blogspot.com/2013/10/planting-trees_1.html

Answer 3

Instead of the sorted linked list i was asked on a sorted array (doesn't matter though logically, but yes run-time varies) to create a BST of minimal height, following is the code i could get out:

typedef struct Node{
     struct Node *left;
     int info;
     struct Node  *right;
}Node_t;

Node_t* Bin(int low, int high) {

     Node_t* node = NULL;
     int mid = 0;

     if(low <= high) {
         mid = (low+high)/2;
         node = CreateNode(a[mid]);
         printf("DEBUG: creating node for %d\n", a[mid]);

        if(node->left == NULL) {
            node->left = Bin(low, mid-1);
        }

        if(node->right == NULL) {
            node->right = Bin(mid+1, high);
        }

        return node;
    }//if(low <=high)
    else {
        return NULL;
    }
}//Bin(low,high)


Node_t* CreateNode(int info) {

    Node_t* node = malloc(sizeof(Node_t));
    memset(node, 0, sizeof(Node_t));
    node->info = info;
    node->left = NULL;
    node->right = NULL;

    return node;

}//CreateNode(info)

// call function for an array example: 6 7 8 9 10 11 12, it gets you desired 
// result

 Bin(0,6); 

HTH Somebody..

Answer 4

You can't do better than linear time, since you have to at least read all the elements of the list, so you might as well copy the list into an array (linear time) and then construct the tree efficiently in the usual way, i.e. if you had the list [9,12,18,23,24,51,84], then you'd start by making 23 the root, with children 12 and 51, then 9 and 18 become children of 12, and 24 and 84 become children of 51. Overall, should be O(n) if you do it right.

The actual algorithm, for what it's worth, is "take the middle element of the list as the root, and recursively build BSTs for the sub-lists to the left and right of the middle element and attach them below the root".

Answer 5

Best isn't only about asynmptopic run time. The sorted linked list has all the information needed to create the binary tree directly, and I think this is probably what they are looking for

Note that the first and third entries become children of the second, then the fourth node has chidren of the second and sixth (which has children the fifth and seventh) and so on...

in psuedo code

read three elements, make a node from them, mark as level 1, push on stack
loop
    read three elemeents and make a node of them
    mark as level 1
    push on stack
    loop while top two enties on stack have same level (n)
         make node of top two entries, mark as level n + 1, push on stack
while elements remain in list

(with a bit of adjustment for when there's less than three elements left or an unbalanced tree at any point)

EDIT:

At any point, there is a left node of height N on the stack. Next step is to read one element, then read and construct another node of height N on the stack. To construct a node of height N, make and push a node of height N -1 on the stack, then read an element, make another node of height N-1 on the stack -- which is a recursive call.

Actually, this means the algorithm (even as modified) won't produce a balanced tree. If there are 2N+1 nodes, it will produce a tree with 2N-1 values on the left, and 1 on the right.

So I think @sgolodetz's answer is better, unless I can think of a way of rebalancing the tree as it's built.

Answer 6

A slightly improved implementation from @1337c0d3r in my blog.

// create a balanced BST using @len elements starting from @head & move @head forward by @len
TreeNode *sortedListToBSTHelper(ListNode *&head, int len) {
    if (0 == len)   return NULL;

    auto left = sortedListToBSTHelper(head, len / 2);
    auto root = new TreeNode(head->val);
    root->left = left;
    head = head->next;
    root->right = sortedListToBSTHelper(head, (len - 1) / 2);
    return root;
}

TreeNode *sortedListToBST(ListNode *head) {
    int n = length(head);
    return sortedListToBSTHelper(head, n);
}