JCH
Java Community | Help. Code. Learn.•2w ago
freekbird

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.
3 Replies
JavaBot
JavaBot•2w ago
⌛ This post has been reserved for your question.
Hey @freekbird! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically marked as dormant after 300 minutes of inactivity.
TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.
freekbird
freekbirdOP•2w ago
What can I do to fix this so it actually works properly
JavaBot
JavaBot•2w ago
💤 Post marked as dormant
This post has been inactive for over 300 minutes, thus, it has been archived. If your question was not answered yet, feel free to re-open this post or create a new one. In case your post is not getting any attention, you can try to use /help ping. Warning: abusing this will result in moderative actions taken against you.

Did you find this page helpful?