Skip to main content

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;
  }
 }
 
 

}

Popular posts from this blog

Watch Live cam on Google!!!!!

Ahhh!!! type certain string in google search bar above and it would bring up the network live cam into your browser. These can be anything from CCTV or webcams... There are lots of string.. i suggest a few down below use them to begin with.. And do come up with your own.. and leave a comment to the post... And ya.. if u come up with something interesting then don forget to share it.. Strings::: Axis cameras: "adding live video to one of your own pages a very easy task with an AXIS 2100 Network Camera" ' google ' intile:"Live view - / - AXIS" ' google ' "Your browser has JavaScript turned off.For the user interface to work effectively" ' google ' inurl:indexFrame.html axis ' google ' "Live web imaging unleashed" ' google ' MOBOTIX cameras: (intext:"MOBOTIX M1" | intext:"MOBOTIX M10") intext:"Open Menu" Shift-Reload ' google ' JVC cameras: "(c)copyright 199...

Most expensive product on Amazon India By Category

Amazon India today has become the most visited e-commerce site in India. So, I decided to analyze the most expensive products that Amazon India Sells across various category. So lets start. Book worth Rs 53,46,000.00 This is quiet modest. I think its a must in every library! DVD worth Rs 40,045.23 My kids are gonna die uneducated :( A Flip Cover worth Rs 255,255.00 I would get around 40 actual Micromax Juice phone at the same price. A pen worth Rs 1,700,000.00 "No doubt a pen is mightier (worthier) then a sword" Telescope worth Rs 896,000.00 This might actually be a fair price. Should understand technical part of it to comment. Help! Spoons worth Rs 2,183,731.00 I might by a house with a kitchen at the same price. Though each spoon would just cost you mere 33,000. Thats a relief! A Game worth Rs 868,434.00 That might be correct again, with import duty on all. I don't know. MultiGym worth Rs...

Problems with mysql.sock

Sometimes while working on Linux, mysql.sock may get deleted by mistake due to some softwares.. in such cases any access to mysql wont be possible as the sock file defines the socket connection for mysql. It will give an error of the following type: ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/var/lib/mysql/mysql.sock' (2) In such cases follow these steps to reconfigure mysql: Delete the log files with the names: ib_logfile0, ib_logfile1 and ibdata1 in the /var/lib/mysql directory Then type: "mysqld_safe --user=mysql &" This will automatically create mysql.sock file and even the new logs files. This is a very simple solution which I used recently and decided to share with you people.