What Is a Binary Search Tree and Its Properties?

TL;DR

A binary search tree is a type of binary tree where every node's left subtree contains only smaller values and its right subtree only larger values, with no duplicate nodes allowed. A quick way to verify one: run an in-order traversal, and if the result is an ascending sorted array, it is a valid BST.

Transcript

Guys in today's video we are going to talk What is binary search tree? So Binary search tree You have studied about binary tree In which we saw, if there is one node over here In that there can be any value. And suppose here I will add a node. And I will make it 11. And after that over here In this way, I will write 6. So this is one type of binary... Read More

Key Insights

• A binary search tree is a type of binary tree, meaning each node can have at most two children, called branches, just like any binary tree structure.
• The core property of a BST is that all nodes of the left subtree are lesser than the node, and all nodes of the right subtree are greater than the node.
• The left-lesser and right-greater rule must hold for all nodes, not just the root, when checking whether a tree qualifies as a binary search tree.
• The left and right subtrees of a BST are themselves binary search trees, a property that becomes automatically satisfied once the lesser and greater conditions hold everywhere.
• A binary search tree does not contain duplicate nodes, because the property uses lesser and greater rather than lesser-or-equal, so equal values cannot exist.
• A tree with root 7 and a left child of 11 is not a BST, because 11 is greater than 7 yet sits in the left subtree, violating the first property.
• In-order traversal of a binary search tree gives an ascending sorted array, which the speaker calls an amazing property useful for checking BST validity.
• To test any tree, compute its in-order traversal and compare keys pairwise; if a later element is smaller than an earlier one, the array is not ascending and it is not a BST.

Questions & Answers

Q: What is a binary search tree?

A binary search tree is a type of binary tree, which means each node can have at most two children or branches. What makes it a binary search tree are its ordering properties: for every node, all nodes in its left subtree are lesser and all nodes in its right subtree are greater. It also does not contain duplicate nodes, and its left and right subtrees are themselves binary search trees.

Q: What are the properties of a binary search tree?

A binary search tree has four properties described in the video. First, all nodes of the left subtree are lesser than the node. Second, all nodes of the right subtree are greater than the node. Third, the left and right subtrees are also binary search trees. Fourth, it does not contain duplicate nodes, since the rule uses lesser and greater rather than lesser-or-equal, so equal values cannot appear.

Q: How do you check if a tree is a binary search tree?

You verify the properties for all nodes, not just the root. For each node, confirm that every node in its left subtree is lesser and every node in its right subtree is greater. The video demonstrates this on a tree with root 9, checking nodes like 4, 11, 7, and 15, and confirms it is a BST because all left values are small and all right values are big at each node.

Q: Why is a tree with root 7 and left child 11 not a binary search tree?

The first property is violated. The root node is 7, but its left child is 11, which is bigger than 7. Since all nodes of the left subtree must be lesser than the node, having 11 on the left breaks the rule. Therefore the answer is no, it is not a binary search tree, because a left subtree node exceeds the root value.

Q: How does in-order traversal help identify a binary search tree?

In-order traversal of a binary search tree gives an ascending sorted array. This means if you are handed any random tree and asked whether it is a BST, you can simply compute its in-order traversal. If the resulting array is in ascending order, it is a binary search tree; if it is not ascending, then it is not a BST. The speaker calls this an amazing and very useful property.

Q: How do you find the in-order traversal of a tree?

The video shows a trick: construct a line in the middle under every node, then sweep across from one side, and whenever you cut through a node, write down its value. Following this on the example tree produces the sequence 2, 4, 5, 7, 8, 9, 11, 14, 15. You must move through the nodes in order without skipping arrows, reading each value as you cross it.

Q: Why does a binary search tree not allow duplicate nodes?

Duplicate nodes are not allowed because the ordering property is defined using lesser and greater, not lesser-or-equal. Since equal values are never written into the rule, two nodes of the same value cannot both satisfy it. If a duplicate did appear, the nodes to the left or right would become equal rather than strictly lesser or greater, which would break the required property, so duplicates are impossible.

Q: Are the subtrees of a binary search tree also binary search trees?

Yes. The third property states that the left and right subtrees of a binary search tree are also binary search trees. The video notes this happens automatically: when all nodes in the left subtree are lesser and all nodes in the right subtree are greater for every node, the subtrees inherently satisfy the same rules, so this property is naturally fulfilled without extra checking.

Summary & Key Takeaways

• A binary search tree is introduced as a type of binary tree, where any root node can have at most two children because binary means two branches. The video builds from prior knowledge of binary trees toward the specific ordering rules that make a tree a BST.

• The defining properties are listed: all nodes of the left subtree are lesser than the node, all nodes of the right subtree are greater, the left and right subtrees are themselves BSTs, and the tree contains no duplicate nodes because equality is excluded.

• Examples demonstrate checking each node against the rules, and an in-order traversal trick is shown: draw a line under each node, sweep across, and read values. If the resulting array is ascending and sorted, the tree is a valid binary search tree.