freekbird Posts - Answer Overflow

freekbird

•Created by freekbird on 3/23/2025 in #java-help

Confused Tree help

I'm a beginner programmer learning about trees currently. I have a question about my confused pointer checker for my tree. The rules that need to be followed are as such: ●The root node’s confused pointer is always null. ● Nodes at odd depth have confused pointers pointing to their parent. ● Nodes at even depth have confused pointers pointing to a random node at the same depth. If there are no other nodes at that depth, it points to null. currently this is what I have:

public boolean isConfusedCorrect(CBTNode root) {
  if (root == null) return true;

  List < CBTNode > currentLevel = new ArrayList < > ();
  currentLevel.add(root);

  int level = 0;

  while (!currentLevel.isEmpty()) {
    List < CBTNode > nextLevel = new ArrayList < > ();
    List < CBTNode > sameLevelNodes = new ArrayList < > ();

    for (CBTNode n: currentLevel) {
      sameLevelNodes.add(n); // adds all the nodes in the current level into sameLevelNodes

      if (n.left != null) nextLevel.add(n.left);
      if (n.right != null) nextLevel.add(n.right);

      if (level == 0) {
        // root node check
        if (n.confused != null) return false; // if it's confused isn't null, then its false
      } else if (level % 2 == 1) {
        // odds check
        if (n.confused == null || (n.confused.left != n && n.confused.right != n)) { // if it's confused isn't equal to it's parent, then its false
          return false;
        }
      } else if (level % 2 == 0) {
        // evens check
        boolean found = false;
        for (CBTNode sameLevelNode: sameLevelNodes) {
          if (n == sameLevelNode.confused) {
            found = true;
            break;
          }
        }
        if (n.confused == null || !found) return false;
      }
    }

    currentLevel = nextLevel;
    level += 1;
  }

  return true;
}

public boolean isConfusedCorrect(CBTNode root) {
  if (root == null) return true;

  List < CBTNode > currentLevel = new ArrayList < > ();
  currentLevel.add(root);

  int level = 0;

  while (!currentLevel.isEmpty()) {
    List < CBTNode > nextLevel = new ArrayList < > ();
    List < CBTNode > sameLevelNodes = new ArrayList < > ();

    for (CBTNode n: currentLevel) {
      sameLevelNodes.add(n); // adds all the nodes in the current level into sameLevelNodes

      if (n.left != null) nextLevel.add(n.left);
      if (n.right != null) nextLevel.add(n.right);

      if (level == 0) {
        // root node check
        if (n.confused != null) return false; // if it's confused isn't null, then its false
      } else if (level % 2 == 1) {
        // odds check
        if (n.confused == null || (n.confused.left != n && n.confused.right != n)) { // if it's confused isn't equal to it's parent, then its false
          return false;
        }
      } else if (level % 2 == 0) {
        // evens check
        boolean found = false;
        for (CBTNode sameLevelNode: sameLevelNodes) {
          if (n == sameLevelNode.confused) {
            found = true;
            break;
          }
        }
        if (n.confused == null || !found) return false;
      }
    }

    currentLevel = nextLevel;
    level += 1;
  }

  return true;
}

So, the issue that i'm coming across is that it always keeps returning false when it should. I've combed through this for a hot minute and I still haven't found the issue.

5 replies

Gaming

Programming