EXERCISE · AlgoCasts
Binary search tree
1) Implement the Node class to create a binary search tree. The constructor should initialize values 'data', 'left', and 'right'.
Directions
1) Implement the Node class to create a binary search tree. The constructor should initialize values 'data', 'left', and 'right'. 2) Implement the 'insert' method for the Node class. Insert should accept an argument 'data', then create an insert a new node at the appropriate location in the tree. 3) Implement the 'contains' method for the Node class. Contains should accept a 'data' argument and return the Node in the tree with the same value.
Try it first#
Copy the stub, make the 4 tests pass on your machine, then open the solution. The reveal is remembered per page in this browser.
class Node {} module.exports = Node;Solution#
class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } insert(data) { if (data < this.data && this.left) { this.left.insert(data); } else if (data < this.data) { this.left = new Node(data); } else if (data > this.data && this.right) { this.right.insert(data); } else if (data > this.data) { this.right = new Node(data); } } contains(data) { if (this.data === data) { return this; } if (this.data < data && this.right) { return this.right.contains(data); } else if (this.data > data && this.left) { return this.left.contains(data); } return null; }} module.exports = Node;const Node = require('./index'); test('Node is a constructor', () => { expect(typeof Node.prototype.constructor).toEqual('function');}); test('Node can insert correctly', () => { const node = new Node(10); node.insert(5); node.insert(15); node.insert(17); expect(node.left.data).toEqual(5); expect(node.right.data).toEqual(15); expect(node.right.right.data).toEqual(17);}); test('Contains returns node with the same data', () => { const node = new Node(10); node.insert(5); node.insert(15); node.insert(20); node.insert(0); node.insert(-5); node.insert(3); const three = node.left.left.right; expect(node.contains(3)).toEqual(three);}); test('Contains returns null if value not found', () => { const node = new Node(10); node.insert(5); node.insert(15); node.insert(20); node.insert(0); node.insert(-5); node.insert(3); expect(node.contains(9999)).toEqual(null);}); Verbatim from the repo at 30cf7634. Alternate tabs are the commented-out solutions with the leading // removed and nothing else changed. Run the tests locally with npx jest bst inside the fork.
See also