Binary Tree

Initialize the binary tree

You can create a tree with the root value. If the root value is not given, an empty node is created and set as a root of the tree.

import { BinaryTree } from "quark-dsa";
 
const tree = new BinaryTree(5); // The binary tree with root value as 5 is created.
const tree2 = new BinaryTree(); // The binary tree is created with root value set as null.

For performing operations on a node in the tree, we need to provide the path of the node. Path of the node should be in the format of L and R. For example, path LRRL means node of having path Left -> Right -> Right -> Left from the root node. Any characters other than L and R with throw an error.

Supported methods

Method	Description	Returns
`getRoot()`	Gets the root of the tree.	Root node of the tree.
`setRootValue(value)`	Sets the given value to the root node.	void
`insertNode(value, path)`	Inserts the value to the given path starting from the root. If the path is an empty string, then it will insert value as a root. Path should be in the form of `L` and `R`. Any characters other than these will throw an error.	Root of the tree
`inorder()`	Performs the inorder traversal on the tree.	List of all node values in inorder manner.
`preorder()`	Performs the preorder traversal on the tree.	List of all node values in preorder manner.
`postorder()`	Performs the postorder traversal on the tree.	List of all node values in postorder manner.
`levelOrder()`	Performs the level order traversal (breadth first search) on the tree.	List of all node values in level order manner.
`height()`	Calculates the height of the tree. Height is the number of edges in the tree from root to the deepest node.	Height of the tree
`nodeHeight()`	Calculates the height of the given node.	Height of the node
`invert()`	Constructs the invert (mirror image) of the given tree.	The root of the inverted tree
`updateNode(value, path)`	Updates the node value of a given path. If the path is an empty string, then it will update the root node value. Path should be in the form of `L` and `R`. Any characters other than these will throw an error.	Root of the tree
`deleteNode(path)`	Deletes the node of a given path. This will delete node and also its children. Path should be in the form of `L` and `R`. Any characters other than these will throw an error.	Root of the tree

Usage

import { BinaryTree } from "quark-dsa";
 
const tree = new BinaryTree(5); // Constructs a tree with 5 as a root node value.
tree.insertNode(3, "L"); // Inserts a node with value 3 on left of root.
tree.insertNode(9, "R"); // Inserts a node with value 9 on right of root.
tree.insertNode(5, "LR"); // Inserts a node with value 5 on right of 3.
tree.insertNode(7, "RL"); // Inserts a node with value 7 on left of 9.
tree.insertNode(6, "RLL"); // Inserts a node with value 6 on left on 7.
tree.insertNode(8, "RLR"); // Inserts a node with value 8 on right on 7.
tree.insertNode(12, "RR"); // Inserts a node with value 12 on right on 9.
tree.insertNode(20, "RRR"); // Inserts a node with value 20 on right on 12.
tree.inorder(); // Should return [3, 5, 5, 6, 7, 8, 9, 12, 20].
tree.preorder(); // Should return [5, 3, 5, 9, 7, 6, 8, 12, 20].
tree.postorder(); // Should return [5, 3, 6, 8, 7, 20, 12, 9, 5].
tree.levelOrder(); // Should return [5, 3, 9, 5, 7, 12, 6, 8, 20].
tree.height(); // Should return 4.
tree.updateNode(13, ""); // Should update root node with value 13.
tree.preorder(); // Should return [13, 3, 5, 9, 7, 6, 8, 12, 20].
tree.updateNode(31, "RLR"); // Updates the node with value 8 with 31.
tree.preorder(); // Should return [13, 3, 5, 9, 7, 6, 31, 12, 20].
tree.deleteNode("RR"); // Should delete the node 12.
tree.inorder(); // Should return [3, 5, 13, 6, 7, 31, 9].
tree.deleteNode("RLL"); // Should delete the node 6.
tree.inorder(); // Should return [3, 5, 13, 7, 31, 9].
tree.invert(); // Construct the invert (mirror) of the tree.
tree.inorder(); // Shoud return [9, 31, 7, 13, 5, 3].

Stack Binarysearchtree