Interview Bootcamp
Vote

0% completed

​

Binary Search Tree (BST)

Binary Search Tree (BST) - Definition and Characteristics

A Binary Search Tree (BST) is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. The BST follows a specific ordering property:

  • The left subtree of a node contains only nodes with values less than the node’s value.
  • The right subtree of a node contains only nodes with values greater than the node’s value.
  • This rule applies recursively to every node in the tree.

.....

.....

.....

Like the course? Get enrolled and start learning!
An Van

An Van

· 2 years ago

For the BST lesson, I think the written text is meant for C++ other language instead of Python. As it is saying Search() is using recursion, while the Python code is using Iteration I'm pretty sure. Just thought I should point out, because it might be confusing for some people

Show 1 reply
Paritosh Paliwal

Paritosh Paliwal

· 2 years ago

In order to meet BST conditions, value of left subtree must be less than or equal to parent node. The insertion code in python3 only checks for < condition but for equals to condition it assigns the node in right subtree.

Correct code should be ?

while current is not None:
    parent = current
    if value > current.data:
        current = current.right
    else:
        current = current.left
Chhangsreng P

Chhangsreng P

· a year ago

In "Tree & Binary Search Tree" section. In the second lesson, it was state

"Binary Search Tree in File Systems: File systems often use BSTs to organize and manage directory structures. The hierarchical nature of BSTs aligns well with the hierarchical structure of directories, enabling efficient file retrieval."

But is that right? A BST is a binary tree, each node having only left or right child, but a file system, a file can have more than 2 sub-files, no? I don't think it's even a binary tree.