Реализация бинарного дерева javascript

Binary Search Tree Algorithms for JavaScript Beginners

I recently had the chance to teach high school students how to code. There are not that many beginner-friendly tutorials on algorithms coded in JavaScript which is the language they were learning. So I decided to make one.

In this article, I will try my best to explain some core algorithms you should learn before a coding interview.

If you are not familiar with the concept of a binary tree, I encourage you to check out the wikipedia page. If you fully master those basic algorithms, you will have an easier time solving more complex problems.

What is a Binary Search Tree (BST)?

Commonly found in coding interviews, BST is a tree-like data structure with a single root at the very top. They are a great way to store numeric values as their ordered nature allows for fast search and lookups.

Compared to a normal tree, BST has the following properties:

• every left child has a smaller value than its parent
• every right child has a larger value than its parent
• every node can contain from 0 to 2 children.

The following diagram should clarify things a bit more.

Definition of a Binary Tree Node

We usually define a Binary Tree Node with the following function in Javascript:

 function TreeNode(val, left, right)

Binary Tree Basic Traversals (Inorder, Postorder, Preorder)

The first thing to know is how to loop through each node of the BST. This allows us to perform a function on all nodes of our BST. For example, if we want to find a value x in our BST, we’d need the nodes.

There are three main ways of doing this. Luckily, they share common themes.

Inorder traversal

A recursive algorithm is the easiest way to get started with binary tree inorder traversal. The idea is as follows:

• If the node is null, do nothing – else, recursively call the function on the node’s left child.
• Then, do some operation on the node after traversing though all left children. Our current node is guaranteed to be the leftest node.
• Finally, call the function on node.right.

The Inorder algorithm traverses the tree nodes from left, to mid, to right.

/** * @param root */ const inorder = (root) => < const nodes = [] if (root) < inorder(root.left) nodes.push(root.val) inorder(root.right) >return nodes > // for our example tree, this returns [1,2,3,4,5,6] 

Postorder traversal

A recursive algorithm is the easiest way to get started with the postorder traversal.

• If the node is null, do nothing – else, recursively call the function on the node’s left child.
• When there are no more left children, call the function on node.right.
• Finally, do some operation on the node.

Postorder traversal visits the tree nodes from left, to right, to mid.

/** * @param root */ const postorder = (root) => < const nodes = [] if (root) < postorder(root.left) postorder(root.right) nodes.push(root.val) >return nodes > // for our example tree, this returns [1,3,2,6,5,4] 

Preorder traversal

A recursive algorithm is the easiest way to get started with the preorder traversal.

• If the node is null, do nothing – else, do some operation on the node.
• Traverse to the left child of the node and repeat.
• Traverse to the right child of node and repeat.

Postorder traversal visits the tree nodes from mid, to left, to right.

/** * @param root */ const preorder = (root) => < const nodes = [] if (root) < nodes.push(root.val) preorder(root.left) preorder(root.right) >return nodes > // for our example tree, this returns [4,2,1,3,5,6] 

What is a Valid Binary Search Tree?

A valid binary search tree (BST) has ALL left children with values less than the parent node, and ALL right children with values greater than the parent node.

To verify if a tree is a valid binary search tree:

• Define the min and max value the current node can have
• If a node’s value is not within those bounds, return false
• Recursively validate the node’s left children, with the max bound set to the node’s value
• Recursively validate the node’s right children, with the min bound set to the node’s value

/** * @param root */ const isValidBST = (root) => < const helper = (node, min, max) =>< if (!node) return true if (node.val = max) return false return helper(node.left, min, node.val) && helper(node.right, node.val, max) > return helper(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER) > 

How to Find Binary Tree Max Depth

Here, the algorithm is attempting to find the height/depth of our BST. In other words, we are looking at how many ‘levels’ a BST contains.

• If the node is null, we return 0 as it does not add any depth
• Else we add + 1 to our current depth (we traversed one level)
• Recursively calculate the depth of node’s children and return the maximum sum between node.left and node.right

/** * @param root */ const maxDepth = function(root) < const calc = (node) => < if (!node) return 0 return Math.max(1 + calc(node.left), 1 + calc(node.right)) >return calc(root) >; 

How to Find the Lowest Common Ancestor Between Two Tree Nodes

Let’s bump up the difficulty. How do we find the common ancestor between two tree nodes in our binary tree? Let’s look at some examples.

In this tree, the lowest common ancestor of 3 and 1 is 2. The LCA of 3 and 2 is 2. The LCA of 6 and 1 and 6 is 4.

See the pattern here? The LCA between two tree nodes is either one of the nodes itself (the case of 3 and 2), or a parent node where the first child is found somewhere in its left subtree, and the second child somewhere in its right subtree.

The algorithm to find the lowest common ancestor (LCA) between two tree nodes p and q is as follows:

• Verify if p or q is found in the left subtree or right subtree
• Then, verify if the current node is p or q
• If one of p or q is found in the left or right subtree, and one of p or q is the node itself, we have found the LCA
• If both p and q are found in the the left or right subtree, we have found the LCA

/** * @param root * @param p * @param q */ const lowestCommonAncestor = function(root, p, q) < let lca = null const isCommonPath = (node) => < if (!node) return false var isLeft = isCommonPath(node.left) var isRight = isCommonPath(node.right) var isMid = node == p || node == q if (isMid && isLeft || isMid && isRight || isLeft && isRight) < lca = node >return isLeft || isRight || isMid > isCommonPath(root) return lca >; 

Wrapping Up

In summary, we have learned how to traverse, verify, and calculate the depth of a BST.

These algorithms are often asked about in coding interviews. It is important to understand them before practicing more advanced BST applications, like finding the LCA of two nodes.

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

License

corocoto/binary-search-tree

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Реализация двоичного дерева поиска на JavaScript

Узел в двоичном дереве (или как его еще называют бинарном) имеет не более двух дочерних элементов: левого и правого элемента. Это определение позволяет вам писать алгоритмы для более эффективной вставки, поиска и удаления узлов.

Двоичное дерево поиска (binary search tree — BST) — это тоже двоичное дерево.

Основное отличие состоит в том, что BST позволяет хранить отсортированные узлы с меньшим значением слева и узлы с большим значением справа.

Обход дерева (Traverse) — это процесс посещения всех узлов дерева и выполнения операции на каждом узле.

Существует три общих подхода:

• Прямой (in-order);
• Симметричный или поперечный (pre-order);
• В обратном порядке (post-order).

При прямом обходе будут посещаться все узлы в порядке возрастания, начиная с указанного узла (хотя это и необязательно), и выполнять заданную функцию обратного вызова callback (также необязательно).

При симметричном обходе посещаются каждый узел до его потомков.

При обходе в обратном порядке посещаются узлы после посещения его потомков.

Метод удаления является наиболее сложным. Его сложность обусловлена различными сценариями, которые нам нужны.

В начале мы ищем соответствующий узел, который нужно удалить, а потом есть три сценария, которые мы рассмотрим более подробно ниже.

Удаление крайнего узла (leaf node)

Первый сценарий включает в себя крайний узел (leaf node), то есть у которого нет левого или правого дочернего элемента. В этом случае нам нужно будет удалить узел, присвоив ему значение null . Однако не стоит забывать, что мы также должны позаботиться о ссылках из родительского узла.

Удаление узла с одним потомком

Второй сценарий включает в себя узел, который имеет левый или правый дочерний узел. Как вы можете видеть на диаграмме ниже, нам нужно пропустить соответствующий узел и назначить родительский указатель на дочерний узел:

Удаление узла с двумя потомками

Третий и последний сценарий включает в себя узел с двумя дочерними элементами. Чтобы удалить такой узел, нужно выполнить следующие действия:

1. Как только вы найдете узел, который нужно удалить, найдите минимальный узел из его правого края поддерева (см. заштрихованную область на диаграмме ниже).
2. Далее вы можете обновить значение узла ключом минимального узла из его правого поддерева. Этим действием вы заменяете ключ узла, что означает, что он будет удален.
3. Теперь у вас есть два узла в дереве с одним и тем же ключом, что не правильно. Таким образом, нужно удалить минимальный узел из правого поддерева, поскольку вы переместили его на место удаленного узла.
4. Наконец, нужно вернуть обновленную ссылку на узел его родителю.

Источник