Question

in javascrift please

Given a pointer to the root of a binary tree write a routine that will delete every node in the tree that is currently a leaf (has no sons), and when finished tell you how many nodes were deleted as well as how many nodes are left in the tree.

Answer 1

Solution

Page 1

script> // Binary Search Tree node: // Node class class Node { constructor(data) { this.data = data; this. left = null; this.right = null; } 14 15 // Binary Search tree class class BinarySearchTree { constructor() { I root of a binary seach tree this.root = null; createNewNode(data) { Il Creating a node and initailising // with data var newNode = new Node(data) // root is null then node will, // be added to the tree and made root. if (this.root === null); this.root = newNode; else I find the correct position in the Il tree and add the node this.insertNode(this.root, newNode);
Page 2

35 36 31 38 39 1/ Method to insert a node in a tree // it iterates over the tree to find the location / at which the new node will be inserted insertNode (node, newNode) { // if the data is less than the node 7 data move left of the tree if (newNode.data < node.data) { // if left is null insert node here if (node. left === null) _ node.left = newNode; else this.insertNode(node.left, newNode); 50 51 52 53 54 // if the data is more than the node // data move right of the tree else { II if right is null insert node here if (node. right === null); node. right = newNode: else this.insertNode(node.right, newNode); 55 56 57 58 59

Page 3

removeLeaf (node) { if (node === null) { return null; leafNodes = 0; // if the tree is empty then 0 leaf nodes // if data to be delete is less than // roots data then move to left subtree, if (node. left === null && node.right === null) { free (node); // if the left and right child of tree are null then there is a leaf node // hence increment the leafNodes count leafNodes++; return null; node. left = this.removeLeaf (node, left); node.right = this.removeLeaf (node.right) return node; // Performs inorder traversal of a tree inorderTraversal(node) { if (node !== null) { this.inorder(node, left); console.log(node.data); this.inorder(node.right); getNodesCount(node) { if (node != null) { this.getNodesCount(node, left); nodesCount++; this.getNodesCount(node.right); return nodesCount; 99 100 101 102 103 104 105 getRootNode() { return this. root; poden
Page 4

טש1 // create an object for the BST var BST = new BinarySearchTree: // insert nodes to the BinarySearchTree BST.createNewNode(15); BST.createNewNode(25) BST.createNewNode(10): BST.createNewNode(7); BST.createNewNode(22); 'BST.createNewNode(17): 'BST.createNewNode(13) BST.createNewNode(5): BST.createNewNode(9) BST.createNewNode(27): 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 I find the root of BST var root = BST.getRootNode(): var nodes Count = 0; var leafNodes = 0; // get the number of nodes in BST nodesCount = BST.getNodesCount (root); I remove leaf nodes from BST BST.removeLeaf (root); console.log("Deleted Nodes :", leafNodes); console.log("Remaining Nodes :", nodesCount - leafNodes): /script>