educative.io

Educative

Much Simpler Logic - passes tests

Do you see a problem with below solution that does not require tracking prev node?

Iterative O(n) Space

class ConnectAllSiblings {
  public static void connect(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while(!queue.isEmpty()) {

      int size = queue.size();

      for(int i=0; i<size; i++) {
        
        TreeNode curr = queue.remove();

        if(curr.left!=null) {
          queue.offer(curr.left);
        }

        if(curr.right!=null) {
          queue.offer(curr.right);
        }

        curr.next = queue.peek();
      }
    }
  }

Iterative O(1) space - this is not simpler but space efficient than the one in the course

class ConnectAllSiblings {
  public static void connect(TreeNode root) {
    
    TreeNode leftmostNode = root;
    TreeNode prevRightmostNode = null;
    while(leftmostNode!=null) {

      TreeNode head = leftmostNode;

      if(prevRightmostNode!=null) {
        prevRightmostNode.next = head;
      }

      while(head!=null) {

        if(head.left!=null) {
          head.left.next = head.right;
        }

        if(head.next!=null) {
          if(head.next.left!=null) {
            if(head.right!=null) {
              head.right.next = head.next.left;
            } else if(head.left!=null) {
              head.left.next = head.next.left;
            }
          } else if(head.next.right!=null) {
            if(head.right!=null) {
              head.right.next = head.next.right;
            } else if(head.left!=null) {
              head.left.next = head.next.right;
            }
          }

        }
        
        if(head.next==null) {
          prevRightmostNode = head;
        }

        head = head.next;
      }

      leftmostNode = leftmostNode.left;
    }

  }

It’s giving errors on my end. Not sure what’s the issue.