Blog

Given a single linked list that has data members arranged in ascending order. Build a balanced binary tree that has the same data members as the given linked list.

Example :

Input:    Linked List 1->3->2
Output: Binary tree 
     3   
   /  \  
  1    2 
pre-order Traversal : 3 ,1 ,2


Input: Linked List 1->3->2->8->5->7->6
Output: Binary tree
        8
      /   \
     3     7
   /  \   / \
  1   2  5   6 
pre-order Traversal : 8 , 3 , 1,  2, 7, 5, 6

Example – Program to convert a linked list to a binary tree

Bellow are the steps , we will follow in this approach.

        1) Find the node in the middle of the list and make it the root of the tree.
        2) Do the same recursively for the left half and the right half.
                a) Get the middle of the left half and make it left child of the root
                   created in step 1.
                b) Get the middle of right half and make it the right child of the
                   root created in step 1.

public class LinkedList {

  static ListNode head;

  class ListNode {
    int data;

    ListNode next, prev;

    ListNode(int d) {
      data = d;
      next = prev = null;
    }
  }

  class TreeNode {
    int data;

    TreeNode left, right;

    TreeNode(int d) {
      data = d;
      left = right = null;
    }
  }

  TreeNode convertListToBTree() {
    int n = countNodes(head);

    /* Construct BST */
    return convertListToBTreeRecursive(n);
  }

  TreeNode convertListToBTreeRecursive(int n) {
    if (n <= 0)
      return null;

    TreeNode left = convertListToBTreeRecursive(n / 2);

    TreeNode root = new TreeNode(head.data);

    root.left = left;

    head = head.next;

    root.right = convertListToBTreeRecursive(n - n / 2 - 1);

    return root;
  }

  /* Function returns count of nodes in a given Linked List */
  int countNodes(ListNode head) {
    int count = 0;
    ListNode temp = head;
    while (temp != null) {
      temp = temp.next;
      count++;
    }
    return count;
  }

  void push(int new_data) {
    ListNode new_node = new ListNode(new_data);

    // prev is always NULL when we are adding at the beginning
    new_node.prev = null;

    /* link the old list off the new node */
    new_node.next = head;

    /* change prev of head node to new node */
    if (head != null)
      head.prev = new_node;

    /* move the head to the new node */
    head = new_node;
  }

  void printList(ListNode node) {
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
  }

  void preOrder(TreeNode node) {
    if (node == null)
      return;
    System.out.print(node.data + " ");
    preOrder(node.left);
    preOrder(node.right);
  }

  public static void main(String[] args) {
    LinkedList list = new LinkedList();

    /* Let us create a linked list will be 1->3->2->8->5->7->6 */
    list.push(1);
    list.push(3);
    list.push(2);
    list.push(8);
    list.push(5);
    list.push(7);
    list.push(6);

    System.out.println("Given Linked List ");
    list.printList(head);

    TreeNode root = list.convertListToBTree();
    System.out.println("");
    System.out.println("Pre-Order Traversal of Binary Tree ");
    list.preOrder(root);
  }
}

Output

Given Linked List
6 7 5 8 2 3 1
Pre-Order Traversal of Binary Tree
8 7 6 5 3 2 1