Convert tree to circular doubly linked list

Question

I want you to pick my code apart and give me some feedback on how I could make it better or simpler. This code converts a binary tree to a doubly linked list (in order).

public class BinaryTreeToLinkedList {
 private TreeNode root;
 private static class TreeNode {
 TreeNode left;
 TreeNode right; 
 int item;
 public TreeNode(TreeNode left, TreeNode right, int item) {
 this.left = left;
 this.right = right;
 this.item = item;
 }
 }
 private TreeNode appendDLL (TreeNode left, TreeNode right) {
 if (left == null) return right;
 if (right == null) return left;
 // get last element of left linkedlist
 TreeNode leftLast = left.left;
 TreeNode rightLast = right.left;
 leftLast.right = right;
 right.left = leftLast;
 // now we form the list into circular again.
 rightLast.right = left;
 left.left = rightLast;
 return left;
 }
 private TreeNode postOrder(TreeNode node) {
 if (node == null) {
 return null;
 }
 TreeNode leftList = postOrder(node.left);
 TreeNode rightList = postOrder(node.right);
 // convert the current node into doubly LL
 node.left = node;
 node.right = node;
 // hook current node.
 leftList = appendDLL (leftList, node);
 // hook right side linkedlist
 leftList = appendDLL (leftList, rightList);
 return leftList;
 }
 public void convertToLinkedList() {
 root = postOrder(root);
 }
 }

• 200_success: Your question says inorder, but your code says postorder.
• JavaDeveloper: Thats not a fault, we need a postorder traversal to fetch inorder linkedlist.

Answer 1

Your code certainly seems to do the job (assuming that the tree is only a root node with two branches; otherwise you will need to implement some recursion). It doesn't "feel" very Java-esque, but you've said in your previous questions/comments that you don't really want critique of method and variable names, so I'll try to avoid that.

if (left == null) return right;
if (right == null) return left;

This code will return null if I pass in null for both left and right. Is that intentional? It's unclear from the way you've written your code that that would be the desired result. When I think about it, it makes sense that the method would return null in this scenario, but I'm not sure if you understood that consequence when you coded it, just based on the style.

if (node == null) {
 return null;
}

You should try to use consistent style in your code. If you're going to put these checks and return statements at the beginning, either put them on the same line as the if() statement or don't. It doesn't matter which you do, as long as you do the same thing throughout. Makes your code much more readable and easier to maintain.

// get last element of left linkedlist
TreeNode leftLast = left.left;
TreeNode rightLast = right.left;
leftLast.right = right;
right.left = leftLast;
// now we form the list into circular again.
rightLast.right = left;
left.left = rightLast;
return left;

This entire block is very difficult to scan. What it does isn't readily apparent by the way you've named all your variables. For example rightLast sounds like the rightmost node in the tree, but in fact it's the left node of the right node in the tree. Then with all the subsequent processing, it's very confusing without stepping through line-by-line to get a better understanding. Consider renaming your variables to be more meaningful. In my opinion, the most beautiful and elegant code is self-documenting.

Also, if you were looking for ways to further improve the code's functionality (besides adding recursion), you might look into generic types so that your nodes can hold any data, rather than just an int.

• JavaDeveloper: Thanks, but rightLast is right most node of tree. Remaining part is a very Helpful feedback.
• asteri: @JavaDeveloper Is it? This line where you declare it seems to say that it's the left node of the current node's right node... (TreeNode rightLast = right.left;)
• JavaDeveloper: Its my bad terminology. right is actually circular linkedlist obtained from right subtree.