Given a binary tree , how do you remove all the half nodes ? | Binary tree node ; For inorder traversal ; Removes all nodes with only one child and returns new root ( note that root may change ) ; if current nodes is a half node with left child NULL left , then it 's right child is  returned and replaces it in the given tree  ; if current nodes is a half node with right child NULL right , then it 's right child is  returned and replaces it in the given tree  ; Driver program
class Node { int data ; Node left , right ; Node ( int item ) { data = item ; left = right = null ; } } class BinaryTree { Node root ; void printInorder ( Node node ) { if ( node != null ) { printInorder ( node . left ) ; System . out . print ( node . data + " ▁ " ) ; printInorder ( node . right ) ; } } Node RemoveHalfNodes ( Node node ) { if ( node == null ) return null ; node . left = RemoveHalfNodes ( node . left ) ; node . right = RemoveHalfNodes ( node . right ) ; if ( node . left == null && node . right == null ) return node ; if ( node . left == null ) { Node new_root = node . right ; return new_root ; } if ( node . right == null ) { Node new_root = node . left ; return new_root ; } return node ; } public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; Node NewRoot = null ; tree . root = new Node ( 2 ) ; tree . root . left = new Node ( 7 ) ; tree . root . right = new Node ( 5 ) ; tree . root . left . right = new Node ( 6 ) ; tree . root . left . right . left = new Node ( 1 ) ; tree . root . left . right . right = new Node ( 11 ) ; tree . root . right . right = new Node ( 9 ) ; tree . root . right . right . left = new Node ( 4 ) ; System . out . println ( " the ▁ inorder ▁ traversal ▁ of ▁ tree ▁ is ▁ " ) ; tree . printInorder ( tree . root ) ; NewRoot = tree . RemoveHalfNodes ( tree . root ) ; System . out . print ( " Inorder traversal of the modified tree "); tree . printInorder ( NewRoot ) ; } }