A binary tree is a very common data structure in computer science and programming. In this article, we will discuss some common features and operations related to binary trees in JavaScript.
Symmetry
Below we will explore how to check whether a binary tree is symmetric using JavaScript. To do this, we will use a recursive function that will perform the verification. We will start by defining a data structure to represent a node in the binary tree.
Let's start by defining the data structure of the binary tree node. Each node will have two main properties: the value of the node and its left and right children.
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
To check whether a binary tree is symmetric, we need to write a recursive function that compares the left and right subtrees of each node. Here's how:
function isSymmetric(root) {
if (!root) {
// If the tree is empty, it is symmetric by definition.
return true;
}
// Helper function for symmetry checking.
function isMirror(left, right) {
if (!left && !right) {
// Both subtrees are empty, so they are symmetric.
return true;
}
if (!left || !right || left.value !== right.value) {
// If one of the subtrees is empty or the values do not match, they are not symmetric.
return false;
}
// Test symmetry recursively.
return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}
// Initial call to helper function.
return isMirror(root.left, root.right);
}
Now that we have defined the isSymmetric function, we can use it to test whether a binary tree is symmetric or not. Here's an example:
// Let's create a sample binary tree:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(2);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(4);
root.right.right = new TreeNode(3);
// Let's check if the tree is symmetric.
const result = isSymmetric(root);
if (result) {
console.log("The tree is symmetric.");
} else {
console.log("The tree is not symmetric.");
}
In this example, the tree is symmetric, so the result will be "The tree is symmetric."
Balancing
A binary tree is a data structure composed of nodes, in which each node can have at most two children: a left child and a right child. A binary tree is considered "balanced" when the height of its left and right subtrees does not differ by more than one unit.
To get started, it is important to understand the structure of a binary tree. Each node in the tree is represented by an object that contains a value and two properties: left (left) and right (right), which represent the children of the node. Binary trees can be represented using a custom JavaScript class, for example:
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
To check whether a binary tree is balanced, we need to calculate the height of the left and right subtrees of each node and check that the difference between these heights is always less than or equal to 1. We can do this using a recursive function.
Here's what a function to check the balance of a binary tree might look like:
function isBalanced(root) {
// Base case: an empty tree is considered balanced
if (!root) {
return true;
}
// Calculate the height of the left and right subtrees
const leftHeight = getHeight(root.left);
const rightHeight = getHeight(root.right);
// Check if the difference between the heights is <= 1
if (Math.abs(leftHeight - rightHeight) <= 1) {
// Continue testing subtrees
return isBalanced(root.left) && isBalanced(root.right);
}
// If the difference between the heights is > 1, the shaft is not balanced
return false;
}
function getHeight(node) {
// Returns the height of a subtree
if (!node) {
return 0;
}
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
In this implementation, the isBalanced function checks whether a tree is balanced or not. To do this, calculate the height of the left and right subtrees using the getHeight function and then check whether the difference between these heights is less than or equal to 1. If the difference
is greater than 1, the tree is not balanced. Otherwise, the function continues to check the left and right subtrees.
Here is an example of using the isBalanced function with a binary tree:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
console.log(isBalanced(root)); // Will return true
In this example, the height of the left subtree is 2, while the height of the right subtree is 1, so the difference is 1, which makes the tree balanced.
Maximum depth
A binary tree is made up of nodes connected to each other. Each node can contain a value and can have at most two children, a left child and a right child. The root is the main node from which the tree begins, while the leaves are the nodes that have no children.
Here is an example of a binary tree structure:
1
/ \
2 3
/ \
4 5
In this example, the root node contains the value 1 and has two children, node 2 and node 3. Node 2 has two children, node 4 and node 5.
To calculate the maximum depth of a binary tree, we can use recursion. The depth of a node is given by the depth of its parent node plus one. Therefore, we can define a recursive function that calculates the maximum depth by visiting all the nodes of the tree.
Here's an example of how to do this in JavaScript:
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function getMaxDepth(root) {
if (!root) {
return 0;
}
const leftDepth = getMaxDepth(root.left);
const rightDepth = getMaxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
// Let's create a sample tree
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
const maxDepth = getMaxDepth(root);
console.log("Maximum tree depth:", maxDepth);
In this code, we created a Node class to represent the nodes of the tree. The getMaxDepth function takes the root of the tree as an argument and calculates the maximum depth using recursion.
Minimum depth
The minimum depth of a binary tree is the length of the shortest path from the root (the top node) to the last leaf node (a node with no children) in the tree. In other words, it represents the minimum number of steps needed to reach the closest leaf from the root.
To calculate the minimum depth of a binary tree, we can use a simple recursive function. Let's start by defining a basic data structure to represent a node in a binary tree:
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
Now, let's create a function that calculates the minimum depth:
function minDepth(root) {
// If the tree is empty, the minimum depth is 0.
if (root === null) {
return 0;
}
// If the current node is a leaf, return 1.
if (root.left === null && root.right === null) {
return 1;
}
// Compute the minimum depth of the left and right subtrees.
const leftDepth = minDepth(root.left);
const rightDepth = minDepth(root.right);
// Return the minimum depth between the left and right subtrees.
return 1 + Math.min(leftDepth, rightDepth);
}
This function is recursive and works like this:
If the tree is empty (represented by
null), the minimum depth is 0.If the current node is a leaf (has no children), the minimum depth is 1.
Otherwise, we calculate the minimum depth of the left and right subtrees by calling the
minDepthfunction recursively over them.Finally, we return 1 plus the minimum between the depths of the left and right subtrees. This represents the minimum depth of the tree.
Here is an example of using the minDepth function with a binary tree:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
const depth = minDepth(root);
console.log("Minimum Depth:", depth); // Output: Minimum Depth: 2
In this example, the binary tree has a minimum depth of 2.
In-order traversal
Among the most common operations that can be performed on a binary tree is traversal, that is, visiting all the nodes of the tree in a specific order. One of the most common ways to traverse a binary tree is in-order traversal.In-order traversal of a binary tree is a type of traversal that follows a specific sequence to visit the nodes of the tree. The in-order traversal order is as follows:
- Visit the left node.
- Visit the root node.
- Visit the right node.
This means that we first visit the left node of the tree, then the root node, and finally the right node. This traversal sequence is very useful when you want to visit all the nodes of a binary tree in an orderly manner, for example when you need to print the nodes in ascending or descending order.
This code creates a simple binary tree and uses the inOrderTraversal function to visit the nodes in order. The result will be the printing of the node values in the correct order: 3, 5, 7, 10, 15.
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function inOrderTraversal(node) {
if (node === null) {
return;
}
inOrderTraversal(node.left);
console.log(node.value);
inOrderTraversal(node.right);
}
const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(3);
root.left.right = new Node(7);
inOrderTraversal(root);
