/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;

class Tree
{
  public static void main(String args[])
    throws Exception
  {
    int arr[] =
    {
      0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
    };
    TreeImpl tree = new TreeImpl();
    tree.insert(100);
    tree.insert(50);
    tree.insert(60);
    tree.insert(150);
    tree.insert(10);
    tree.insert(5);
    tree.insert(140);
    tree.insert(200);
    tree.insert(210);
    tree.inorderTraversal();
    tree.removeHalfNodes(tree.root, null, null);
    tree.inorderTraversal();

  }
}

class TreeImpl
{
  public Node root;
  Node curr;

  public boolean isHalfNode(Node root)
  {
    if (root == null)
      return false;
    if ((root.left != null && root.right == null) || (root.left == null && root.right != null))
    {
      return true;
    }
    return false;
  }

  public void removeHalfNodes(Node root, Node parent, Boolean isLeft)
  {
    while (isHalfNode(root))
    {
      if (root.left != null && root.right == null)
      {
        if (isLeft)
        {
          parent.left = root.left;
        }
        else
        {
          parent.right = root.left;
        }
        root = root.left;
      }
      if (root.left == null && root.right != null)
      {
        if (isLeft)
        {
          parent.left = root.right;
        }
        else
        {
          parent.right = root.right;
        }
        root = root.right;
      }
    }
    if (root == null)
      return;
    removeHalfNodes(root.left, root, true);
    removeHalfNodes(root.right, root, false);

  }

  class Node
  {
    private Integer data;
    private Node right;
    private Node left;

    public Node()
    {
    }

    public Node(Integer data)
    {
      this.data = data;
    }
  }


  public void insert(Integer data)
  {
    if (root == null)
    {
      root = new Node(data);
      return;
    }
    Node temp1 = root, temp2 = null;
    boolean left = false, right = false;
    while (temp1 != null)
    {
      temp2 = temp1;
      left = false;
      right = false;
      if (temp1.data.compareTo(data) > 0)
      {
        left = true;
        temp1 = temp1.left;
      }
      else
      {
        right = true;
        temp1 = temp1.right;
      }
    }
    if (left)
    {
      temp2.left = new Node(data);
    }
    else if (right)
    {
      temp2.right = new Node(data);
    }

  }

  public void putDataInTree(Integer data, Node root)
  {
    if (root != null)
    {
      if (root.data.compareTo(data) > 0)
      {
        putDataInTree(data, root.left);
      }
      else
      {
        putDataInTree(data, root.right);
      }
    }
    else
    {
      root = new Node(data);
    }
  }


  public void inorderTraversal()
  {
    inorderTraversal(root, 0);
    System.out.println(sumMap);
  }
  Map<Integer, Integer> sumMap = new HashMap<Integer, Integer>();

  public void inorderTraversal(Node root, int dis)
  {
    if (root != null)
    {
      inorderTraversal(root.left, dis + 1);
      Integer sumTillNow = sumMap.get(dis);
      if (sumTillNow == null)
        sumTillNow = 0;
      sumTillNow = sumTillNow + root.data;
      sumMap.put(dis, sumTillNow);
      System.out.print(root.data + " ");
      inorderTraversal(root.right, dis);
    }
  }



}