Tuesday, October 14, 2014

Flatten a Binary Search Tree into a LinkedList in Java

package com.biplav.algorithms;

public class FlattenBST {
 
 public static class TreeNode {
  public TreeNode left;
  public TreeNode right;
  public int value;
  public TreeNode(TreeNode left, TreeNode right, int value) {
   super();
   this.left = left;
   this.right = right;
   this.value = value;
  }
  
 }
 
 public static class ListNode {
  public ListNode next;
  public int value;
  public ListNode(ListNode next, int value) {
   super();
   this.next = next;
   this.value = value;
  }  
 }
 
 public static ListNode flatten(TreeNode root) {
  ListNode left = root.left != null ? flatten(root.left) : null;
  ListNode base = new ListNode(null,root.value);
  ListNode right = root.right != null ? flatten(root.right) : null; 
  base.next = right != null ? right : null;
  if(left == null) return base;
  else {
   ListNode home = left;
   while(left.next != null) left = left.next;
   left.next= base;
   return home;
  }
 }
 /*
  *          6
  *      3       8
  *   2    4   7  10
  */
 
 public static void main(String[] args) {
  TreeNode t3 = new TreeNode(null, null, 2);
  TreeNode t2 = new TreeNode(null, null, 4);
  TreeNode t4 = new TreeNode(t3, t2, 3);
  TreeNode t7 = new TreeNode(null, null, 7);
  TreeNode t10 = new TreeNode(null, null, 10);
  TreeNode t8 = new TreeNode(t7, t10, 8);
  TreeNode t6 = new TreeNode(t4, t8, 6);
  ListNode root = flatten(t6);
  while(root != null) {
   System.out.println(root.value);
   root = root.next;
  }
 }
 
 

}