Member Avatar for ilovejava

This is my code for adding and removing from a binary tree but apparently its not complete can anyone tell me what to do to make it complete tree?

public void add(IBinaryTreeNode<E> e) {
		
		if (getRoot() == null) {
			setRoot(e);
		} else {
			//SAME HERE
			IBinaryTreeNode<E> node = getLastNode();
			node.setRightChild(e);
			e.setParent(node);
		}
		setLastNode(e);
		setSize(getSize() + 1);
	}
	@Override
	public IBinaryTreeNode<E> remove() {
		
		IBinaryTreeNode<E> node = getLastNode();
		if (!node.equals(getRoot())) {
			//IM SURE SOMETHING WRONG HERE
			node.getParent().setRightChild(null);
			setLastNode(node.getParent());
		} else {
			setLastNode(null);
			setRoot(null);
		}
		node.setParent(null);
		setSize(getSize() - 1);
		return node;
	}
  • 3 Contributors
  • 3 Replies
  • 271 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by Member #887084

Dani AI

Generated

The problem is an algorithmic one rather than an exception: was right to ask for errors, but absence of crashes usually means the tree invariants are wrong. ’s add always attaches the new node as a right child of whatever getLastNode() returns, and the remove unconditionally clears parent.setRightChild(null). As pointed out, that leaves left links dangling and produces the right-skewed shape instead of a complete tree.

A complete binary tree must be filled level-by-level, left-to-right. Two simple, reliable approaches:

  • Array-backed (recommended): keep nodes (or values) in an ArrayList in level order. When inserting, append and compute the parent with parentIndex = (newIndex - 1) / 2; attach as left if newIndex == 2*parentIndex+1 else right. When removing, remove the last element and clear the corresponding left/right link of its parent. This makes add/remove O(1) amortized and keeps last trivial to compute.

Example (outline):

private List<IBinaryTreeNode<E>> nodes = new ArrayList<>();

public void add(IBinaryTreeNode<E> node) {
    if (nodes.isEmpty()) { setRoot(node); nodes.add(node); return; }
    int idx = nodes.size();
    int parentIdx = (idx - 1) / 2;
    IBinaryTreeNode<E> parent = nodes.get(parentIdx);
    if (2 * parentIdx + 1 == idx) parent.setLeftChild(node);
    else parent.setRightChild(node);
    node.setParent(parent);
    nodes.add(node);
}

public IBinaryTreeNode<E> remove() {
    if (nodes.isEmpty()) return null;
    int lastIdx = nodes.size() - 1;
    IBinaryTreeNode<E> node = nodes.remove(lastIdx);
    if (lastIdx == 0) { setRoot(null); return node; }
    int parentIdx = (lastIdx - 1) / 2;
    IBinaryTreeNode<E> parent = nodes.get(parentIdx);
    if (2 * parentIdx + 1 == lastIdx) parent.setLeftChild(null);
    else parent.setRightChild(null);
    node.setParent(null);
    return node;
}
  • Pointer-based alternative: maintain a queue (or deque) of candidate parents (nodes with <2 children). On insert, peek front; attach left if missing else attach right and pop front when both children are present; also push the new node into the queue.

Troubleshooting tips: print level-order after each operation to verify "left-to-right" filling; add unit tests for the first 10 inserts/removes and assert parent/child indexes using the array-index formula; avoid trying to maintain lastNode alone unless also tracking full level-order history (an array or queue is simpler).

Recommended Answers

All 3 Replies

Member Avatar for hbluthi

Post error code you receive when code crashes

Member Avatar for ilovejava

I do not receive any errors but my tree is shifting to the right i want to figure out way to make it a complete binary tree

Member Avatar for Member #887084

//IM SURE SOMETHING WRONG HERE

Yes.

Consider this tree:

root
         /     \
    node1       node2
    /   \        /   \
node3  node4  node5  node6

Using your code, if I remove node1 this is what happens:

I get root and I set root's right to null (what?). Then I set the node's parent to null. However, root still has a left reference to the deleted node (that's not right either).

How are you ordering your nodes and balancing your tree? This is important as it determines whether node4 should take node1's spot, or whether node3 should take node1's spot, or whether the root should take node1's spot.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.