HTML preprocessors can make writing HTML more powerful or convenient. For instance, Markdown is designed to be easier to write and read for text documents and you could write a loop in Pug.

In CodePen, whatever you write in the HTML editor is what goes within the `<body>`

tags in a basic HTML5 template. So you don't have access to higher-up elements like the `<html>`

tag. If you want to add classes there that can affect the whole document, this is the place to do it.

In CodePen, whatever you write in the HTML editor is what goes within the `<body>`

tags in a basic HTML5 template. If you need things in the `<head>`

of the document, put that code here.

!
##### Insecure Resource

The resource you are linking to is using the 'http' protocol, which may not work when the browser is using https.

CSS preprocessors help make authoring CSS easier. All of them offer things like variables and mixins to provide convenient abstractions.

It's a common practice to apply CSS to a page that styles elements such that they are consistent across all browsers. We offer two of the most popular choices: normalize.css and a reset. Or, choose **Neither** and nothing will be applied.

To get the best cross-browser support, it is a common practice to apply vendor prefixes to CSS properties and values that require them to work. For instance `-webkit-`

or `-moz-`

.

We offer two popular choices: Autoprefixer (which processes your CSS server-side) and -prefix-free (which applies prefixes via a script, client-side).

Any URLs added here will be added as `<link>`

s in order, and before the CSS in the editor. You can use the CSS from another Pen by using its URL and the proper URL extension.

You can apply CSS to your Pen from any stylesheet on the web. Just put a URL to it here and we'll apply it, in the order you have them, before the CSS in the Pen itself.

You can also link to another Pen here (use the `.css`

URL Extension) and we'll pull the CSS from that Pen and include it. If it's using a *matching* preprocessor, use the appropriate URL Extension and we'll combine the code before preprocessing, so you can use the linked Pen as a true dependency.

+ add another resource

JavaScript preprocessors can help make authoring JavaScript easier and more convenient.

Babel includes JSX processing.

Any URL's added here will be added as `<script>`

s in order, and run *before* the JavaScript in the editor. You can use the URL of any other Pen and it will include the JavaScript from that Pen.

You can apply a script from anywhere on the web to your Pen. Just put a URL to it here and we'll add it, in the order you have them, before the JavaScript in the Pen itself.

If the script you link to has the file extension of a preprocessor, we'll attempt to process it before applying.

You can also link to another Pen here, and we'll pull the JavaScript from that Pen and include it. If it's using a matching preprocessor, we'll combine the code before preprocessing, so you can use the linked Pen as a true dependency.

+ add another resource

Search for and use JavaScript packages from npm here. By selecting a package, an `import`

statement will be added to the top of the JavaScript editor for this package.

Using packages here is powered by esm.sh, which makes packages from npm not only available on a CDN, but prepares them for native JavaScript ESM usage.

All packages are different, so refer to their docs for how they work.

If you're using React / ReactDOM, make sure to turn on Babel for the JSX processing.

If active, Pens will autosave every 30 seconds after being saved once.

If enabled, the preview panel updates automatically as you code. If disabled, use the "Run" button to update.

If enabled, your code will be formatted when you actively save your Pen. **Note: your code becomes un-folded during formatting.**

Visit your global Editor Settings.

` ````
<div class="alert alert-note">
<h1>
Binary Search Tree Implementation
</h1>
<p>
A binary tree in which for each node, value of all the nodes in the left subtree is lesser or equal and value of all the nodes in the right subtree is greater than the root node.
<br>
<img src="https://i.imgur.com/DYkRBqz.png">
</p>
<p>
<h3>Height of the Tree</h3>
<li> Height of the leaf node is 0 </l>
<li> Height of an empty tree is -1 </l>
<li> Height is number of edges from root node to the given node.</l>
<li> Height of the root node is the height of the tree. </li>
<p>
<img src="https://i.imgur.com/7D2w9IC.png" alt="BST height">
</p>
</p>
<p>
<b> Heap</b> is a dynamic memory.
Local variables of functions are stored in <b> Stack</b>. Whenever a function finishes the stack frame is reclaimed.
</p>
<p>
<h3>Search</h3>
<p>
<h4>Recursive Search</h4>
Time Complexity: O(log (n)), Space Complexity: O(log (n))
</p>
<p>
<h4>Iterative Search</h4>
Time Complexity: O(log (n)), Space Complexity: O(1)
</p>
</p>
<p>
<h3>
Insert
</h3>
<b>
O(Log(n)) time | Space O(h) where h is the height of the tree
</b><br>
For 1 insert operation, avg case is O(lgn) and worst case is O(n) <br>
For n insert operations, avg case is O(nlgn) and worst case is O(n^2)
</p>
<p>
<h3>
Delete
</h3>
<b>
O(Log(n)) time | Space O(h) where h is the height of the tree
</b><br>
<li>
<strong>Case 1: No child</strong>
</li>
<li>
<strong>Case 2: One child</strong>
</li>
<li>
<strong>Case 3: Two child</strong>
Find Minimum in the right subtree copy the value in the targeted node. Delete the duplicate from right-subtree.
</li>
<br>
<img src="https://i.imgur.com/VuruDcG.png" alt="delete node in bst">
</p>
</div>
```

` ````
.alert {
padding: 20px;
border-radius: 25px;
margin-bottom: 15px;
}
.alert-tip {
background-color: #def6dd;
}
.alert-note {
background-color: #efd9fd;
overflow-x: auto;
}
pre {
overflow-x: auto;
white-space: pre-wrap;
white-space: -moz-pre-wrap;
white-space: -pre-wrap;
white-space: -o-pre-wrap;
word-wrap: break-word;
}
```

` ````
/*
Nodes are created in the heap seciton of the memory
Address of the root node we keep for a tree.
*/
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
/*
O(Log(n)) time | Space O(h) where h is the height of the tree
For 1 insert operation, avg case is O(lgn) and worst case is O(n)
For n insert operations, avg case is O(nlgn) and worst case is O(n^2)
*/
function insertRecursively(root, data) {
// If the tree is empty create new node.
if (root == null) root = new Node(data);
else if (data <= root.data) root.left = insert(root.left, data);
else root.right = insert(root.right, data);
return root;
}
/*
O(Log(n)) time | Space O(1)
For 1 insert operation, avg case is O(log(n)) and worst case is O(n)
For n insert operations, avg case is O(nlgn) and worst case is O(n^2)
*/
function insert(root, data) {
const nodeToInsert = new Node(data);
if (root == null) return nodeToInsert;
let current = root;
let previous = root;
while (current != null) {
previous = current;
if (data <= current.data) current = current.left;
else current = current.right;
}
if (data <= previous.data) previous.left = nodeToInsert;
else previous.right = nodeToInsert;
return root;
}
// O(log n) time | space O(1)
function remove(root, data) {
if (root == null) return root;
else if (data < root.data) root.left = remove(root.left, data);
else if (data > root.data) root.right = remove(root.right, data);
else {
// found the node.
// case 1: no child
if (root.left == null && root.right == null) {
root = null;
} else if (root.left == null) {
// case 2: One child
let current = root;
root = root.right;
current = null;
} else if (root.right == null) {
let current = root;
root = root.left;
current = null;
} else {
// case 3: Two child
let current = findMin(root.right);
root.data = current.data;
root.right = remove(root.right, current.data);
}
}
return root;
}
// O(log(n)) time | O(log (n))
function searchRecursive(root, data) {
if (root == null) return false;
else if (data === root.data) return true;
else if (data <= root.data) return search(root.left, data);
else return search(root.right, data);
}
// O(log(n)) time | O(log (n))
function search(root, data) {
while (root != null) {
if (data === root.data) return true;
else if (data <= root.data) root = root.left;
else root = root.right;
}
return false;
}
function findMin(root) {
if (root == null) return root;
while (root.left) {
root = root.left;
}
return root.data;
}
function findMax(root) {
if (root == null) return root;
while (root.right) {
root = root.right;
}
return root.data;
}
// O(n) time | (O log(n)) space
function findHeight(root) {
if (root == null) return -1; // empty tree height is -1
return Math.max(findHeight(root.left), findHeight(root.right)) + 1;
}
describe("In Binary Search Tree", () => {
it("I can insert", () => {
let root = null;
root = insert(root, 15);
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 25);
root = insert(root, 8);
root = insert(root, 12);
expect(root).toBeTruthy();
});
it("I can insert recursively", () => {
let root = null;
root = insertRecursively(root, 15);
root = insertRecursively(root, 10);
root = insertRecursively(root, 20);
root = insertRecursively(root, 25);
root = insertRecursively(root, 8);
root = insertRecursively(root, 12);
expect(root).toBeTruthy();
});
});
describe("I can perform below operations in BST", () => {
let root = null;
beforeEach(() => {
root = null;
root = insert(root, 15);
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 25);
root = insert(root, 8);
root = insert(root, 12);
});
it("I can search recursively", () => {
expect(searchRecursive(root, 8)).toBeTruthy();
expect(searchRecursive(root, 22)).toBeFalsy();
});
it("I can search iteratively", () => {
expect(search(root, 8)).toBeTruthy();
expect(search(root, 22)).toBeFalsy();
});
it("I can find Minimum in BST", () => {
expect(findMin(root)).toBe(8);
});
it("I can find Maximum in BST", () => {
expect(findMax(root)).toBe(25);
});
it("I can find Height of BST", () => {
expect(findHeight(root)).toBe(2);
});
it("I can find Delete 8 from BST", () => {
remove(root, 8);
expect(search(root, 8)).toBeFalsy();
});
});
```

999px

Also see: Tab Triggers