How do I properly traverse a tree with a "current" or "temp" node and assign?

Question

I have a binary tree that the root only has a left child. I am making methods to insert, delete and search the tree. My strategy is to make a temporary node called "current" and assign my root value to it at the start of each method. With this "current" node I traverse my tree looking for the correct spot to insert or delete nodes. My line of current = newNode is what I thought would insert my newNode into the tree.

When I test to see if it works, I try to print root.leftChild.leftChild.name to see if it inserted, but it comes up null.

public void insertDate(String flight, String date) {
    current = root.leftChild;
    Node newNode = new Node(date);

    while (current != null) {
        if (current.name == flight) {
            current = current.leftChild;
            while (current != null) {
                current = current.rightChild;
            }
            current = newNode;
            return;
        }
        current = current.rightChild;
    }
}

Drawing of tree

This code works here:

public void addFlight(String flight) {
    current = root;
    Node newNode = new Node(flight);

    if (current.leftChild == null) {
        current.leftChild = newNode;
        System.out.println(flight + " has been added!");
    } else {
        current = current.leftChild;
        while (current.rightChild != null) {
            current = current.rightChild;
        }
        current.rightChild = newNode;
        System.out.println(flight + " has been added!");
    }
}

Does this answer your question? [Is Java "pass-by-reference" or "pass-by-value"?](https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) — tgdavies, Nov 25 '21 at 03:57
It might I'm going to check that out, I have code similar to what I have written that works, so not sure what I'm doing wrong. — Jon, Nov 25 '21 at 04:00
Assigning `newNode` to `current` changes only the value of `current` -- it doesn't change the child field of any other node. — tgdavies, Nov 25 '21 at 04:02
I just added another method to my original question, and this method works. — Jon, Nov 25 '21 at 04:02
Ok what is the difference between doing `current = root` `current.rightChild = newNode` compared to doing `current = root.rightChild` `current = newNode`. Do both of these work the same? — Jon, Nov 25 '21 at 04:30
`current.rightChild = newNode` assigns `newNode` to the `rightChild` field of whichever `Node` `current` is a reference to. `current = newNode` makes the local variable `current` refer to whatever `Node` `newNode` is a reference to. — tgdavies, Nov 25 '21 at 05:10

plalx · Answer 1 · 2021-11-26T04:59:51.513

The problem is that current = newNode just reassign the current local variable's value, it doesn't set the rightChild of the latest date note found which is the wanted insertion point.

Change:

current = newNode;
return;

for:

current.rightChild = newNode;
return;

On another node you'd greatly benefit from breaking down the problem into sub-problems:

Find flight node
Find latest date node right before the insertion date
Insert date node

const flightTree = {
  left: {
    flight: 'Flight 1',
    right: {
      flight: 'Flight 2',
      left: { 
        date: new Date(10),
        right: {
          date: new Date(20),
          right: {
            date: new Date(30)
          }
        }
      }
    }
  }
};

insertFlightDate(flightTree, 'Flight 2', new Date(1));
insertFlightDate(flightTree, 'Flight 2', new Date(25));
insertFlightDate(flightTree, 'Flight 1', new Date(10));
insertFlightDate(flightTree, 'Flight 1', new Date(20));

console.log(JSON.stringify(flightTree, null, 4));

function insertFlightDate(flightTree, flight, newDate) {
  const flightNode = findFlight(flightTree.left, flight);
  
  if (!flightNode) throw new Error('flight not found');
  
  const newDateNode = { date: newDate };
  const dateNodeBeforeNewDate = latestDateNodeBefore(flightNode.left, newDate);
  
  if (!dateNodeBeforeNewDate) {
    const next = flightNode.left;
    flightNode.left = newDateNode;
    newDateNode.right = next;
    return;
  }
  
  const next = dateNodeBeforeNewDate.right;
  dateNodeBeforeNewDate.right = newDateNode;
  newDateNode.right = next;
}

function findFlight(flightNode, flight) {
  if (!flightNode) return null;
  if (flightNode.flight === flight) return flightNode;
  
  return findFlight(flightNode.right, flight);
}

function latestDateNodeBefore(dateNode, searchDate) {
  if (!dateNode || dateNode.date > searchDate) return null;
  return latestDateNodeBefore(dateNode.right, searchDate) || dateNode;
}

How do I properly traverse a tree with a "current" or "temp" node and assign?

1 Answers1