Java PreOrder + Queue solution


  • 30

    Hi all, I think my solution is pretty straightforward and easy to understand, not that efficient though. And the serialized tree is compact.
    Pre order traversal of BST will output root node first, then left children, then right.

    root left1 left2 leftX right1 rightX
    

    If we look at the value of the pre-order traversal we get this:

    rootValue (<rootValue) (<rootValue) (<rootValue) |separate line| (>rootValue) (>rootValue)
    

    Because of BST's property: before the |separate line| all the node values are less than root value, all the node values after |separate line| are greater than root value. We will utilize this to build left and right tree.

    Pre-order traversal is BST's serialized string. I am doing it iteratively.
    To deserialized it, use a queue to recursively get root node, left subtree and right subtree.

    I think time complexity is O(NlogN).
    Errr, my bad, as @ray050899 put below, worst case complexity should be O(N^2), when the tree is really unbalanced.

    My implementation

    public class Codec {
        private static final String SEP = ",";
        private static final String NULL = "null";
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            if (root == null) return NULL;
            //traverse it recursively if you want to, I am doing it iteratively here
            Stack<TreeNode> st = new Stack<>();
            st.push(root);
            while (!st.empty()) {
                root = st.pop();
                sb.append(root.val).append(SEP);
                if (root.right != null) st.push(root.right);
                if (root.left != null) st.push(root.left);
            }
            return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        // pre-order traversal
        public TreeNode deserialize(String data) {
            if (data.equals(NULL)) return null;
            String[] strs = data.split(SEP);
            Queue<Integer> q = new LinkedList<>();
            for (String e : strs) {
                q.offer(Integer.parseInt(e));
            }
            return getNode(q);
        }
        
        // some notes:
        //   5
        //  3 6
        // 2   7
        private TreeNode getNode(Queue<Integer> q) { //q: 5,3,2,6,7
            if (q.isEmpty()) return null;
            TreeNode root = new TreeNode(q.poll());//root (5)
            Queue<Integer> samllerQueue = new LinkedList<>();
            while (!q.isEmpty() && q.peek() < root.val) {
                samllerQueue.offer(q.poll());
            }
            //smallerQueue : 3,2   storing elements smaller than 5 (root)
            root.left = getNode(samllerQueue);
            //q: 6,7   storing elements bigger than 5 (root)
            root.right = getNode(q);
            return root;
        }
    }
    

  • 6
    R

    I think deserialize the time complexity is O(n^2) worst, see this case:
    4
    /
    3
    /
    2
    /
    1
    Then we have T(n) = T(n) * T(n - 1) =O (n^2)

    Correct me if I am wrong.

    Thanks


  • 0

    @ray050899 Hey, you're right! Thanks for pointing out.


  • 0
    F

    Could you tell me how you handle null. Eg, [1,2, null,3].


  • -1
    R

    What is the number can be the same?


  • 0

    @rosaic said in Java PreOrder + Queue solution:

    What is the number can be the same?

    Good point, but I guess we don't have to worry about that here, BST by definition doesn't allow this situation to happen.
    I am not too sure on this though...


  • 1

    @jiahaofang123
    Just go through the code please, I think it's straight forward enough :)


  • 1
    I

    @magicshine
    I think the code did not handle null child either. In serialize, if a node's child is null, it will not be pushed into stack. Null root is handled though.


  • 0

    @iamthewind I don't think the null needs to be serialised. Null children will be created when we deserialize the string.


  • 0
    E

    very beautiful method with deep understanding of BST's sorted order property!


  • 2

    @EurekaSevenPlusPlus Wow, thank you for the kind word! But really, I was just stealing ideas from other BST posts, wish I could go back and identify the source sometime later. Will update a source credit when I see it.


  • 0
    A

    Here is my deseralize().
    Its very similar to the above mentioned solution, as both use recursion to create BST from pre-ordered serialized string. While mines throws java.lang.StackOverflowError, but the one mentioned above works like a charm. I would appreciate if any one can point out why ?

      // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data.equals("")) return null;
            String[] splits = data.split(",");
            return createBST(splits, 0, splits.length-1);
        }
        
        private TreeNode createBST(String[] splits, int start, int end){
            if(end == splits.length || start > end) return null;
            TreeNode root = new TreeNode(Integer.valueOf(splits[start]));
            int endLeft = start + 1;
            while (endLeft < end && 
                        Integer.valueOf(splits[endLeft]) <= Integer.valueOf(splits[start])) endLeft++;
    
            root.left = createBST(splits, start+1, endLeft);
            root.right = createBST(splits, endLeft+1, end);
            return root;
        }
    

  • 6
    K

    The solution is similiar with mine;But I think my code is more concise:

    
        public String serialize(TreeNode root) {
    	if (root == null) {
    	    return "#!";
    	}
    	String res = root.val + "!";
    	res += serialize(root.left);
    	res += serialize(root.right);
    	return res;
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
        	String[] strings = data.split("!");
        	LinkedList<String> list = new LinkedList<>();
        	for (String string:strings){
        	    list.add(string);
        	}
            return reconPreOrder(list);
        }
        
        public TreeNode reconPreOrder(LinkedList<String> queue){
        	String val = queue.poll();
        	if (val.equals("#")) {
        	    return null;
    	}
        	TreeNode head = new TreeNode(Integer.valueOf(val));
        	head.left = reconPreOrder(queue);
        	head.right = reconPreOrder(queue);
        	return head;
        }
    

  • 0

    @kelvinlulu awesome, I think it's a much better implementation, thanks!


  • 0

    @ashwath Hey sorry, it's been a while. Do you still need help with it?


  • 1
    P

    @magicshine I think there is no BST property being used here. We can apply the exact same logic to serialize and deserialize a normal Binary tree. Don't you agree ?
    And why is worst case complexity is O(N^2) here ? I think it should be O(N) because every node is being visited once. Although there are some extra null nodes but that won't increase it to more than O(2N). Correct me if I am wrong.


  • 1

    @piyush121 Hey, I added some lines to explain how the solution takes advantage of BST property.

    For time complexity, the costly (bar raiser) operation here would be the getNode() operation. It's a divide-and-conquer like algorithm, which is run twice (one on the left branch, the other one on right branch) (like merge-sort). Each time reducing the size of the problem by half. So usually the time complexity would be O(NlogN).

    For the unbalanced situation, where the tree only has one branch (left or right), the size of the problem would not be halved. So here time complexity would be O(N^2).

    Hope this helps!


  • 1
    P

    @magicshine Hey, I am sorry but I was talking about the @kelvinlulu's Solution.


  • 0

    @piyush121 Hahaha, it's alright! Thanks for asking, I got a chance to revisit my solution here.


  • 0
    P

    @magicshine SO what are your thought's on @kelvinlulu's solution ? Is it O(N) ?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.