#562

Committed 18 Jun 2023 05:07PM UTC coverage: 97.602%. First build

Build # #562

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

Merge pull request #207 from Ahtaxam/master

Add 3-sum problem with improvement issue #208

Run Details

525 of 541 branches covered (97.04%)

Branch coverage included in aggregate %.

21 of 21 new or added lines in 1 file covered. (100.0%)

1266 of 1294 relevant lines covered (97.84%)

32.93 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.85

/src/_DataStructures_/Trees/BinarySearchTree/utils.js

const Node = require('./Node');

const utils = {
  // eslint-disable-next-line consistent-return
  insert(root, value) {
    if (root === null) {
      const newNode = new Node(value);
      // eslint-disable-next-line no-param-reassign
      root = newNode;
      return root;
    }

    if (value < root.value) {
      // eslint-disable-next-line no-param-reassign
      root.leftChild = this.insert(root.leftChild, value);
      return root;
    }
    if (value > root.value) {
      // eslint-disable-next-line no-param-reassign
      root.rightChild = this.insert(root.rightChild, value);
      return root;
    }
  },

  preorder(root, array) {
    if (root === null) return array;
    array.push(root.value);
    this.preorder(root.leftChild, array);
    this.preorder(root.rightChild, array);
    return array;
  },

  inorder(root, array) {
    if (root === null) return array;
    this.inorder(root.leftChild, array);
    array.push(root.value);
    this.inorder(root.rightChild, array);
    return array;
  },

  postorder(root, array) {
    if (root === null) return array;
    this.postorder(root.leftChild, array);
    this.postorder(root.rightChild, array);
    array.push(root.value);
    return array;
  },

  // eslint-disable-next-line consistent-return
  search(root, value) {
    if (root === null) return false;
    if (value === root.value) return true;

    if (value < root.value) {
      return this.search(root.leftChild, value);
    }
    if (value > root.value) {
      return this.search(root.rightChild, value);
    }
  },

  delete(root, value) {
    if (root === null) {
      return root;
    }

    if (value > root.value) {
      // eslint-disable-next-line no-param-reassign
      root.rightChild = this.delete(root.rightChild, value);
    } else if (value < root.value) {
      // eslint-disable-next-line no-param-reassign
      root.leftChild = this.delete(root.leftChild, value);
    } else {
      // found the node
      if (root.leftChild === null) {
        // there is a right sub-tree
        return root.rightChild;
      }
      if (root.rightChild === null) {
        // there is a left sub-tree
        return root.leftChild;
      }
      /**
       * the root contain 2 childs, we got 2 options:
       * 1. We can either find the Node with minimum value at from the right sub-tree
       * 2. Or, we can find the Node with maximum value from the left sub-tree
       *
       * I'm picking up 1 here
       */
      const minRightNode = this.findMinNode(root.rightChild);
      // eslint-disable-next-line no-param-reassign
      root.value = minRightNode.value;
      // eslint-disable-next-line no-param-reassign
      root.rightChild = this.delete(root.rightChild, minRightNode.value);
      return root;
    }
    return root;
  },

  findMinNode(root) {
    /** The minnimum values is the let most leaf node in BST */
    if (root.leftChild === null) return root;
    return this.findMinNode(root.leftChild);
  },

  findMaxNode(root) {
    if (root.rightChild === null) return root;
    return this.findMaxNode(root.rightChild);
  },
};

module.exports = utils;

1	const Node = require('./Node');	3✔
2
3	const utils = {	3✔
4	// eslint-disable-next-line consistent-return
5	insert(root, value) {
6	if (root === null) {	259✔
7	const newNode = new Node(value);	90✔
8	// eslint-disable-next-line no-param-reassign
9	root = newNode;	90✔
10	return root;	90✔
11	}
12
13	if (value < root.value) {	169✔
14	// eslint-disable-next-line no-param-reassign
15	root.leftChild = this.insert(root.leftChild, value);	93✔
16	return root;	93✔
17	}
18	if (value > root.value) {	76✔
19	// eslint-disable-next-line no-param-reassign
20	root.rightChild = this.insert(root.rightChild, value);	71✔
21	return root;	71✔
22	}
23	},
24
25	preorder(root, array) {
26	if (root === null) return array;	45✔
27	array.push(root.value);	21✔
28	this.preorder(root.leftChild, array);	21✔
29	this.preorder(root.rightChild, array);	21✔
30	return array;	21✔
31	},
32
33	inorder(root, array) {
34	if (root === null) return array;	57✔
35	this.inorder(root.leftChild, array);	26✔
36	array.push(root.value);	26✔
37	this.inorder(root.rightChild, array);	26✔
38	return array;	26✔
39	},
40
41	postorder(root, array) {
42	if (root === null) return array;	45✔
43	this.postorder(root.leftChild, array);	21✔
44	this.postorder(root.rightChild, array);	21✔
45	array.push(root.value);	21✔
46	return array;	21✔
47	},
48
49	// eslint-disable-next-line consistent-return
50	search(root, value) {
51	if (root === null) return false;	7✔
52	if (value === root.value) return true;	6✔
53
54	if (value < root.value) {	5✔
55	return this.search(root.leftChild, value);	1✔
56	}
57	if (value > root.value) {	4!
58	return this.search(root.rightChild, value);	4✔
59	}
60	},
61
62	delete(root, value) {
63	if (root === null) {	36✔
64	return root;	1✔
65	}
66
67	if (value > root.value) {	35✔
68	// eslint-disable-next-line no-param-reassign
69	root.rightChild = this.delete(root.rightChild, value);	7✔
70	} else if (value < root.value) {	28✔
71	// eslint-disable-next-line no-param-reassign
72	root.leftChild = this.delete(root.leftChild, value);	11✔
73	} else {
74	// found the node
75	if (root.leftChild === null) {	17✔
76	// there is a right sub-tree
77	return root.rightChild;	14✔
78	}
79	if (root.rightChild === null) {	3✔
80	// there is a left sub-tree
81	return root.leftChild;	1✔
82	}
83	/**
84	* the root contain 2 childs, we got 2 options:
85	* 1. We can either find the Node with minimum value at from the right sub-tree
86	* 2. Or, we can find the Node with maximum value from the left sub-tree
87	*
88	* I'm picking up 1 here
89	*/
90	const minRightNode = this.findMinNode(root.rightChild);	2✔
91	// eslint-disable-next-line no-param-reassign
92	root.value = minRightNode.value;	2✔
93	// eslint-disable-next-line no-param-reassign
94	root.rightChild = this.delete(root.rightChild, minRightNode.value);	2✔
95	return root;	2✔
96	}
97	return root;	18✔
98	},
99
100	findMinNode(root) {
101	/** The minnimum values is the let most leaf node in BST */
102	if (root.leftChild === null) return root;	9✔
103	return this.findMinNode(root.leftChild);	5✔
104	},
105
106	findMaxNode(root) {
107	if (root.rightChild === null) return root;	7✔
108	return this.findMaxNode(root.rightChild);	5✔
109	},
110	};
111
112	module.exports = utils;	3✔

knaxus / problem-solving-javascript / #562

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous