Commitbd5a16b

authored and

committed

Fix BST removal method (trekhleb#74)

* Fix LinkedList* Fix the prepend method for the LinkedList* Fix the remove method for the MinHeap* Correct a comment* Fix BST removal method

1 parente558231 commitbd5a16bCopy full SHA for bd5a16b

File tree

+26

-7

lines changed

src/data-structures/tree/binary-search-tree
- BinarySearchTreeNode.js
- __test__
  - BinarySearchTreeNode.test.js

+26

-7

lines changed

Lines changed: 11 additions & 7 deletions

Original file line number	Diff line number	Diff line change
`@@ -94,8 +94,13 @@ export default class BinarySearchTreeNode extends BinaryTreeNode {`
`94`	`94`
`95`	`95`	`if(!nodeToRemove.left&&!nodeToRemove.right){`
`96`	`96`	`// Node is a leaf and thus has no children.`
`97`		`-// Just remove the pointer to this node from the parent node.`
`98`		`-parent.removeChild(nodeToRemove);`
	`97`	`+if(parent){`
	`98`	`+// Node has a parent. Just remove the pointer to this node from the parent.`
	`99`	`+parent.removeChild(nodeToRemove);`
	`100`	`+}else{`
	`101`	`+// Node has no parent. Just erase current node value.`
	`102`	`+nodeToRemove.value=null;`
	`103`	`+}`
`99`	`104`	`}elseif(nodeToRemove.left&&nodeToRemove.right){`
`100`	`105`	`// Node has two children.`
`101`	`106`	`// Find the next biggest value (minimum value in the right branch)`
`@@ -113,11 +118,10 @@ export default class BinarySearchTreeNode extends BinaryTreeNode {`
`113`	`118`	`}else{`
`114`	`119`	`// Node has only one child.`
`115`	`120`	`// Make this child to be a direct child of current node's parent.`
`116`		`-if(nodeToRemove.left){`
`117`		`-parent.replaceChild(nodeToRemove,nodeToRemove.left);`
`118`		`-}else{`
`119`		`-parent.replaceChild(nodeToRemove,nodeToRemove.right);`
`120`		`-}`
	`121`	`+constchild=nodeToRemove.left\|\|nodeToRemove.right;`
	`122`	`+nodeToRemove.value=child.value;`
	`123`	`+nodeToRemove.setLeft(child.left);`
	`124`	`+nodeToRemove.setRight(child.right);`
`121`	`125`	`}`
`122`	`126`
`123`	`127`	`returntrue;`

Lines changed: 15 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -185,6 +185,21 @@ describe('BinarySearchTreeNode', () => {`
`185`	`185`	`expect(bstRootNode.toString()).toBe('30');`
`186`	`186`	`});`
`187`	`187`
	`188`	`+it('should remove node with no parent',()=>{`
	`189`	`+constbstRootNode=newBinarySearchTreeNode();`
	`190`	`+expect(bstRootNode.toString()).toBe('');`
	`191`	`+`
	`192`	`+bstRootNode.insert(1);`
	`193`	`+bstRootNode.insert(2);`
	`194`	`+expect(bstRootNode.toString()).toBe('1,2');`
	`195`	`+`
	`196`	`+bstRootNode.remove(1);`
	`197`	`+expect(bstRootNode.toString()).toBe('2');`
	`198`	`+`
	`199`	`+bstRootNode.remove(2);`
	`200`	`+expect(bstRootNode.toString()).toBe('');`
	`201`	`+});`
	`202`	`+`
`188`	`203`	`it('should throw error when trying to remove not existing node',()=>{`
`189`	`204`	`constbstRootNode=newBinarySearchTreeNode();`
`190`	`205`

Comments

(0)