Scribd
Upload
145 views2 pages

Binary Search Tree Essentials

A binary search tree is a binary tree where each node only contains nodes with keys less than its key to the left, and nodes with keys greater than its key to the right. It allows for searching, insertion, and deletion in O(log n) time on average but worst case O(n) time. The maximum number of nodes in a binary search tree of height h is 2h+1− 1.

Uploaded by

Akhil Madavan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
145 views2 pages

Binary Search Tree Essentials

A binary search tree is a binary tree where each node only contains nodes with keys less than its key to the left, and nodes with keys greater than its key to the right. It allows for searching, insertion, and deletion in O(log n) time on average but worst case O(n) time. The maximum number of nodes in a binary search tree of height h is 2h+1− 1.

Uploaded by

Akhil Madavan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

BINARY SEARCH TREE

Imp formula

inner nodes = leaf nodes−1

 The left subtree of a node contains only nodes with keys less than the node's key.
 The right subtree of a node contains only nodes with keys greater than the node's key.
 The left and right subtree each must also be a binary search tree.
 Each node can have up to two successor nodes.
 There must be no duplicate nodes.
 A unique path exists from the root to every other node.

Difference between binary tree and binary search tree


Binary tree: In short, a binary tree is a tree where each node has up to two leaves. In a binary
tree, a left child node and a right child node contain values which can be either greater, less,
or equal to parent node.

3
/ \
4 5

Binary Search Tree: In binary search tree, the left child contains nodes with values less than
the parent node and where the right child only contains nodes with values greater than or
equal to the parent.
4
/ \
3 5

Average Worst case


Space O(n) O(n)
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
The maximum number of nodes is a binary tree of
height h is
2h+1− 1

You might also like