Saturday, May 14, 2016

Convert binary tree in to doubly linked list (Java Code)

package com.salpe;

import java.util.logging.Logger;

import org.junit.Test;

public class BSTTest {

 private static final Logger s_logger = Logger.getLogger(BSTTest.class.getName());

 @Test
 public void test() {

  // create test data 
  BSTNode<Integer> node0 = new BSTNode<>(0, null, null);
  BSTNode<Integer> node2 = new BSTNode<>(2, null, null);
  BSTNode<Integer> node01 = new BSTNode<>(1, node0, node2);

  // create BST 
  BST<Integer> bst = new BST<>(node01);

  // convert BST to doubly linked list;
  BSTNode<Integer> head = bst.toDoublyLinkedlIst();

  while (head != null) {

   s_logger.info(" --> "+head.data.toString());

   head = head.right;
  }

 }

 /**
  * Binary Tree Node model 
  *
  * @param <T>
  */
 static class BSTNode<T extends Comparable<T>> {

  T data;
  BSTNode<T> left;
  BSTNode<T> right;

  BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {

   this.data = data;
   this.left = left;
   this.right = right;

  }

  @Override
  public String toString() {
   return "BSTNode [data=" + data + "]";
  }

 }

 /**
  * Binary Tree Representation 
  *
  * @param <T>
  */
 static class BST<T extends Comparable<T>> {

  BSTNode<T> root;

  public BST(BSTNode<T> root) {
   this.root = root;
  }

  public BSTNode<T> toDoublyLinkedlIst() {

   BSTNode<T> tail = toDoublyLinkedlIst0(root);
   
   // get head of linked list ;
   
   BSTNode<T> head = tail;

   while (head.left != null) {

    head = head.left;
   }
   return head;

  }

  public BSTNode<T> toDoublyLinkedlIst0(BSTNode<T> node) {

   if (node.left == null && node.right == null) {

    return node;
   }

   BSTNode<T> nodeLeft = toDoublyLinkedlIst0(node.left);
   nodeLeft.right = node;

   BSTNode<T> nodeRight = toDoublyLinkedlIst0(node.right);
   nodeRight.left = node;

   // returns tail or right most element 
   return nodeRight;

  }

 }

}

No comments: