CODEWITHSUNDEEP
javatreestack-overflow
Shambhavi Srivastava
Shambhavi Srivastava

Reputation: 21

Getting stackoverflow error on inverting a binary tree using a global variable

I am trying to invert a binary tree as in Java:

class Solution {
    TreeNode node;
    public TreeNode invertTree(TreeNode root) 
    {
        if(root == null)
            return null;

        node = root;

        node.left = invertTree(root.right);

        node.right = invertTree(root.left);

        return node;
    }
}

However on running this code I am getting a stackoverflow error. Can anyone explain why?

Upvotes: 1

Views: 99

Answers (2)

Dimpy Aggarwal
Dimpy Aggarwal

Reputation: 21

After inverting left subtree and right subtree, you need to swap the left node and right node too to make an inverted binary tree. You just need to add the code of swap two values.

class Solution {
TreeNode node;
public TreeNode invertTree(TreeNode root) 
    {
    if(root == null)
        return root;


    invertTree(root.left);
    invertTree(root.right);

     TreeNode temp=root.left;
     root.left=root.right;
    root.right=temp;

    return node;
    }
}

Upvotes: 0

Harshal Parekh
Harshal Parekh

Reputation: 6017

You need to create new nodes and replace them while parsing. You are trying to use one TreeNode object to do so, therefore you never reach your base condition.

To understand better, please use a pretty print method and call it from this method and observe the change on small input.

 public TreeNode invertTree(TreeNode root) {
    if (root == null){
        return root;
    }

    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);

    root.left = right;
    root.right = left;

    return root;
}

The inverse of a tree with root r, and subtrees right and left, is a tree with root r, whose right subtree is the inverse of left, and whose left subtree is the inverse of right.

Upvotes: 1

Related Questions