CODEWITHSUNDEEP
javarecursion
spyair
spyair

Reputation: 57

Why does this recursion function only set once?

I know that recursion keeps being executed till it meets the base case.

However, why does this recursion function only set head's child once?

When the head becomes null, it returns the node and sets the head's either left child or right child as node.

I get this concept, but why doesn't this recursion function sets all the left children or right children as nodes even though it's recursion function?

One more question, this recursion stops when the head is null, but why doesn't this recursion set null's child as node? this recursion sets previous of null's head's child as node. Why is it?

public Node<Integer> insert(Node<Integer> head, Node<Integer> node){
    if(head == null){
        return node;
    }

    if(head.getData() >= node.getData()){
        head.setLeftChild(insert(head.getLeftChild(), node));
    } else {
        head.setRightChild(insert(head.getRightChild(), node));
    }

    return head;
}

Upvotes: 0

Views: 89

Answers (2)

krukid
krukid

Reputation: 4525

What we have here is a binary search tree insertion function.

The function takes two nodes as parameters: head being the root of the binary tree, and node is the new node you are inserting into it.

The new node will be inserted in such a way that a depth-first in-order traversal of the tree will yield an ascending sequence of integers.

why does this recursion function only set head's child once?

It sets all tree nodes along the path from root node to inserted node's position on the way out of recursion. Only the first assignment is meaningful though, because all others just set the same node without change.

why doesn't this recursion function sets all the left children or right children as nodes even though it's recursion function?

Each call of the function in this recursion sets left, right or no child. If you follow the execution carefully, you will see at which position in the tree which child is set.

why doesn't this recursion set null's child as node?

The recursion exit condition prevents any operations on a head if it's value is null - it returns the node that you want to insert instead to the previous recursion call where the actual insertion takes place.

Upvotes: 2

Eran
Eran

Reputation: 393966

insert returns in most cases head. Whenever it returns head, head.setLeftChild(insert(head.getLeftChild(), node)) results in head.setLeftChild(head.getLeftChild()) and head.setRightChild(insert(head.getRightChild(), node)) results in head.setRightChild(head.getRightChild()). i.e. in most cases, the calls to setLeftChild and setRightChild don't change the left/right child of the current head Node.

Only when insert(head.getLeftChild(), node) or insert(head.getRightChild(), node)) is passed a null value (i.e. when head.getLeftChild() or head.getRightChild() are null), the recursive call returns the new Node, node, which causes head.setLeftChild(insert(head.getLeftChild(), node)) to result in head.setLeftChild(node) and head.setRightChild(insert(head.getRightChild(), node)) to result in head.setRightChild(node).

Upvotes: 1

Related Questions