Google Interview Question Java Developers
0of 0 votesconvert a Sorted linkedList to complete BST
Country: United States
public class Solution {
public static TreeNode list2BST(ListNode head) {
if ( head == null ) return null;
return toBST(head, null);
}
public static TreeNode toBST(ListNode head, ListNode tail ) {
ListNode slow = head;
ListNode fast = head;
while( fast != tail && fast.next != tail ) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode current = new TreeNode(slow.val);
current.left = toBST(head, slow);
current.right = toBST(slow.next, tail);
return current;
}
}
package main
import (
"fmt"
"math"
)
type LList struct {
val int
next *LList
}
type Tree struct {
val int
left *Tree
right *Tree
}
func convert(head *LList) *Tree {
tmp := head
count := 0
for tmp != nil {
count++
tmp = tmp.next
}
if count == 0 {
return nil
}
return convertHelper(head, count)
}
func convertHelper(head *LList, count int) *Tree {
if count == 0 {
return nil
}
if count == 1 {
return &Tree{val: head.val}
}
levels := uint(math.Log2(float64(count)))
full := 1<<levels - 1
lastLevel := count - full
if lastLevel > (full+1)/2 {
lastLevel = (full + 1) / 2
}
middle := (full-1)/2 + lastLevel
middleOrig := middle
tmp := head
for middle > 0 {
tmp = tmp.next
middle--
}
root := &Tree{val: tmp.val}
root.left = convertHelper(head, middleOrig)
root.right = convertHelper(tmp.next, count-1-middleOrig)
return root
}
func main() {
head := fillList(13)
printList(head)
fmt.Println()
printLevelTree(convert(head))
}
func height(root *Tree) int {
if root == nil {
return 0
}
lh := height(root.left)
rh := height(root.right)
if lh < rh {
return rh + 1
} else {
return lh + 1
}
}
func printLevelTree(root *Tree) {
h := height(root)
for i := 1; i <= h; i++ {
printGivenLevel(root, i)
fmt.Println()
}
}
func printGivenLevel(root *Tree, level int) {
if root == nil {
return
}
if level == 1 {
fmt.Print(root.val, " ")
return
}
printGivenLevel(root.left, level-1)
printGivenLevel(root.right, level-1)
}
func fillList(count int) *LList {
var head *LList
for i := count; i > 0; i-- {
newNode := &LList{val: i, next: head}
head = newNode
}
return head
}
func printList(root *LList) {
for root != nil {
fmt.Print(root.val, " ")
root = root.next
}
}
My code produces a balanced BST, but not necessary a complete one.
O(N) time.
Node *BuildBst(LLNode *head, int size)
{
if (size <= 0) {
return NULL;
}
LLNode *ll_n = head;
int left_size = 0;
for (int i = 0; i < size / 2; ++i) {
ll_n = ll_n->next_;
++left_size;
}
Node *n = new Node(ll_n->val_);
n->left_ = BuildBst(head, left_size);
n->right_ = BuildBst(ll_n->next_, size - left_size - 1);
return n;
}
This is my O(n) time solution. It is recursive so uses O(logn) stack space.
It first computed tree height etc. and then does in-order recursion till it reaches tree height, creating nodes in order (smallest value node first and so on).
Other solutions that I see here, that use recursion by first creating root node (using slow and fast pointers), are O(nlogn) time.
//binary tree node
struct BTNode{
int value;
BTNode* left = nullptr;
BTNode* right = nullptr;
};
//linked list node
struct LLNode{
int value;
LLNode* next = nullptr;
};
//recursive function
BTNode* sortedLinkedListToCompleteBinaryTree(LLNode** current_llnode, int depth, int* current_height, int num_extra_leaves, int* num_extra_leaves_visited){
//recurse left if we are not at the leaf node
BTNode* left_child = nullptr;
if(depth < *current_height){
left_child = sortedLinkedListToCompleteBinaryTree(current_llnode, depth + 1, current_height, num_extra_leaves, num_extra_leaves_visited);
}
//create tree node with value of the current linked list node and progress current linked list node
BTNode *node = new BTNode();
node->left = left_child;
node->value = (*current_llnode)->value;
*current_llnode = (*current_llnode)->next;
//check if we filled in all the extra leaf nodes
if(*num_extra_leaves_visited < num_extra_leaves){
if(depth == *current_height){
++(*num_extra_leaves_visited);
//if we right now filled all the extra leaves we now have to fill rest of the tree that is one less in height
if(*num_extra_leaves_visited == num_extra_leaves){
--(*current_height);
}
}
}
//recurse right if we are not at the leaf node
if(depth < *current_height){
node->right = sortedLinkedListToCompleteBinaryTree(current_llnode, depth + 1, current_height, num_extra_leaves, num_extra_leaves_visited);
}
return node;
}
BTNode* sortedLinkedListToCompleteBinaryTree(LLNode* head){
LLNode* tail = head;
//get total number of nodes
int num_nodes = 1;
while(tail->next != nullptr){
tail = tail->next;
++num_nodes;
}
//get number of digits in binary to get size of perfect tree (greatest power of 2-1 <= total nodes)
int num_binary_digits = 0;
int num_nodes_copy = num_nodes;
do{
num_nodes_copy >>= 1;
++num_binary_digits;
}while(num_nodes_copy != 0);
int num_nodes_perfect = (1<<num_binary_digits)-1;
//num digits in binary equals to tree height for perfect tree
int num_digits_perfect = num_binary_digits;
if(num_nodes_perfect > num_nodes){
num_nodes_perfect >>= 1;
--num_digits_perfect;
}
int perfect_height = num_digits_perfect;
//number of extra leaves in bottom level (that make tree not perfect)
int num_extra_leaves = num_nodes - num_nodes_perfect;
//height of the whole tree
int max_height = perfect_height;
if(num_extra_leaves > 0){
++max_height;
}
//this variable tracks current maximum depth to which we recurse (should get decreased by 1 when we fill all the extra leaves)
int current_height = max_height;
int num_extra_leaves_visited = 0;
//we do in-order recursion (because our linked list it ordered) and track current linked list node
LLNode* current_llnode = head;
BTNode* root = sortedLinkedListToCompleteBinaryTree(¤t_llnode, 1, ¤t_height, num_extra_leaves, &num_extra_leaves_visited);
return root;
}
public class ListToBSTConversion {
public static int[] convert(List<Integer> sortedList) {
int[] tree = new int[sortedList.size()];
recurse(sortedList, tree, 0, sortedList.size(), 0);
return tree;
}
private static void recurse(List<Integer> sortedList, int[] tree, int start,
int end, int nextPosition) {
if (nextPosition < sortedList.size()) {
int middle = (start + end) / 2;
tree[nextPosition] = sortedList.get(middle);
recurse(sortedList, tree, start, middle, 2 * nextPosition + 1);
recurse(sortedList, tree, middle, end, 2 * nextPosition + 2);
}
}
public static void main(String args[]) {
List<Integer> sortedList = Arrays.asList(new Integer[] { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
System.out.println(Arrays.toString(convert(sortedList)));
}
}
#include <iostream>
#include <queue>
using namespace std;
struct node{
int value;
node* next;
};
struct treenode{
int value;
treenode* left;
treenode* right;
};
void PrintLinkedList(node* head)
{
while(head!= NULL)
{
cout<<head->value<<"->";
head = head->next;
}
cout<<"NULL"<<endl;
}
void PrintBST(treenode* head)
{
if(head == NULL)
{
return;
}
int new_count = 1;
queue<treenode*> q;
q.push(head);
while(q.size() != 0)
{
int count = new_count;
new_count = 0;
for(int i=0; i<count; i++)
{
treenode* parent = q.front();
q.pop();
if(parent->left != NULL)
{
q.push(parent->left);
new_count++;
}
if(parent->right != NULL)
{
q.push(parent->right);
new_count++;
}
cout<<parent->value<<" ";
}
cout<<endl;
}
}
int Length(node* head)
{
int length = 0;
while(head!= NULL)
{
length++;
head = head->next;
}
return length;
}
int Power(int x, int count)
{
int y = x;
for(int i=0; i<count-1; i++)
{
x = x * y;
}
return x;
}
int GetLevel(int length)
{
int level = 0;
int x = 2;
while(x*2 <= length)
{
level++;
x=x*2;
}
return level;
}
treenode* ToBST(node* head, int length)
{
if(length == 1)
{
treenode* newnode = new treenode();
newnode->value = head->value;
return newnode;
}
if(length == 2)
{
treenode* newnode = new treenode();
newnode->value = head->next->value;
newnode->left = new treenode();
newnode->left->value = head->value;
return newnode;
}
int level = GetLevel(length);
int firstSubTree = Power(2, level) - 1;
int leaves = firstSubTree + 1;
int total = length - 1;
int secondSubTree;
if(total - firstSubTree > firstSubTree)
{
secondSubTree = firstSubTree;
total = total - 2*firstSubTree;
if(total - leaves > 0)
{
firstSubTree = firstSubTree + leaves;
secondSubTree = secondSubTree + total - leaves;
}
else
{
firstSubTree = firstSubTree + total;
}
}
else
{
secondSubTree = total - firstSubTree;
}
node* left = head;
for(int i=0; i<firstSubTree-1; i++)
{
left = left-> next;
}
treenode* current = new treenode();
current->value = left->next->value;
node* right = left->next->next;
left->next->next = NULL;
left->next = NULL;
current->left = ToBST(head, firstSubTree);
current->right = ToBST(right, secondSubTree);
return current;
}
treenode* ConvertLinkedListToCompleteBST(node* head)
{
if(head == NULL)
{
return NULL;
}
int length = Length(head);
treenode* root = ToBST(head, length);
return root;
}
int main() {
node* head = new node();
head->value = 1;
head->next = new node();
head->next->value = 2;
head->next->next = new node();
head->next->next->value = 3;
head->next->next->next = new node();
head->next->next->next->value = 4;
PrintLinkedList(head);
treenode* root = ConvertLinkedListToCompleteBST(head);
PrintBST(root);
}
you have used ArrayList, but the question asks to use LinkedList
- Sabbir Manandhar February 26, 2018