fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8.  
  9. import java.util.ArrayList;
  10. import java.util.Arrays;
  11. import java.util.HashMap;
  12. import java.util.Iterator;
  13. import java.util.LinkedHashMap;
  14. import java.util.List;
  15. import java.util.ListIterator;
  16. import java.util.Map;
  17.  
  18. class Tree
  19. {
  20.   public static void main(String args[])
  21.     throws Exception
  22.   {
  23.     int arr[] =
  24.     {
  25.       0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
  26.     };
  27.     TreeImpl tree = new TreeImpl();
  28.     tree.insert(100);
  29.     tree.insert(50);
  30.     tree.insert(60);
  31.     tree.insert(150);
  32.     tree.insert(10);
  33.     tree.insert(5);
  34.     tree.insert(140);
  35.     tree.insert(200);
  36.     tree.insert(210);
  37.     tree.inorderTraversal();
  38.     tree.removeHalfNodes(tree.root, null, null);
  39.     tree.inorderTraversal();
  40.  
  41.   }
  42. }
  43.  
  44. class TreeImpl
  45. {
  46.   public Node root;
  47.   Node curr;
  48.  
  49.   public boolean isHalfNode(Node root)
  50.   {
  51.     if (root == null)
  52.       return false;
  53.     if ((root.left != null && root.right == null) || (root.left == null && root.right != null))
  54.     {
  55.       return true;
  56.     }
  57.     return false;
  58.   }
  59.  
  60.   public void removeHalfNodes(Node root, Node parent, Boolean isLeft)
  61.   {
  62.     while (isHalfNode(root))
  63.     {
  64.       if (root.left != null && root.right == null)
  65.       {
  66.         if (isLeft)
  67.         {
  68.           parent.left = root.left;
  69.         }
  70.         else
  71.         {
  72.           parent.right = root.left;
  73.         }
  74.         root = root.left;
  75.       }
  76.       if (root.left == null && root.right != null)
  77.       {
  78.         if (isLeft)
  79.         {
  80.           parent.left = root.right;
  81.         }
  82.         else
  83.         {
  84.           parent.right = root.right;
  85.         }
  86.         root = root.right;
  87.       }
  88.     }
  89.     if (root == null)
  90.       return;
  91.     removeHalfNodes(root.left, root, true);
  92.     removeHalfNodes(root.right, root, false);
  93.  
  94.   }
  95.  
  96.   class Node
  97.   {
  98.     private Integer data;
  99.     private Node right;
  100.     private Node left;
  101.  
  102.     public Node()
  103.     {
  104.     }
  105.  
  106.     public Node(Integer data)
  107.     {
  108.       this.data = data;
  109.     }
  110.   }
  111.  
  112.  
  113.   public void insert(Integer data)
  114.   {
  115.     if (root == null)
  116.     {
  117.       root = new Node(data);
  118.       return;
  119.     }
  120.     Node temp1 = root, temp2 = null;
  121.     boolean left = false, right = false;
  122.     while (temp1 != null)
  123.     {
  124.       temp2 = temp1;
  125.       left = false;
  126.       right = false;
  127.       if (temp1.data.compareTo(data) > 0)
  128.       {
  129.         left = true;
  130.         temp1 = temp1.left;
  131.       }
  132.       else
  133.       {
  134.         right = true;
  135.         temp1 = temp1.right;
  136.       }
  137.     }
  138.     if (left)
  139.     {
  140.       temp2.left = new Node(data);
  141.     }
  142.     else if (right)
  143.     {
  144.       temp2.right = new Node(data);
  145.     }
  146.  
  147.   }
  148.  
  149.   public void putDataInTree(Integer data, Node root)
  150.   {
  151.     if (root != null)
  152.     {
  153.       if (root.data.compareTo(data) > 0)
  154.       {
  155.         putDataInTree(data, root.left);
  156.       }
  157.       else
  158.       {
  159.         putDataInTree(data, root.right);
  160.       }
  161.     }
  162.     else
  163.     {
  164.       root = new Node(data);
  165.     }
  166.   }
  167.  
  168.  
  169.   public void inorderTraversal()
  170.   {
  171.     inorderTraversal(root, 0);
  172.     System.out.println(sumMap);
  173.   }
  174.   Map<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
  175.  
  176.   public void inorderTraversal(Node root, int dis)
  177.   {
  178.     if (root != null)
  179.     {
  180.       inorderTraversal(root.left, dis + 1);
  181.       Integer sumTillNow = sumMap.get(dis);
  182.       if (sumTillNow == null)
  183.         sumTillNow = 0;
  184.       sumTillNow = sumTillNow + root.data;
  185.       sumMap.put(dis, sumTillNow);
  186.       System.out.print(root.data + " ");
  187.       inorderTraversal(root.right, dis);
  188.     }
  189.   }
  190.  
  191.  
  192.  
  193. }
  194.  
  195.  
Success #stdin #stdout 0.11s 320256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5 10 50 60 100 140 150 200 210 {0=660, 1=250, 2=10, 3=5}
5 50 60 100 140 150 210 {0=1120, 1=500, 2=15, 3=5}
https://ideone.com/HpMcSm
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!