Binary Search Tree
Python
Algorithmic thinking
Data structures
Public
Python
Python is a widely used, high-level, general-purpose, interpreted, dynamic programming language. Having a basic familiarity with the programming language used on the job is a prerequisite for quickly getting up to speed.
Algorithmic thinking
When designing and/or analyzing an algorithm or data structure, it is important to consider the performance and structure of an implementation. Algorithmic thinking is one of the key traits of a good programmer, especially one working on complex or performance-critical code.
Data structures
Choosing the right data structure to solve a problem can have huge implications on the performance of an application. Knowing when to use a specific data structure is one of the most important skills for a programmer.
Public
Public questions (free account) are common interview questions. They are great for practicing, or if you want to filter candidates using the classic problems.
Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree.
Write a function that, efficiently with respect to time used, checks if a given binary search tree contains a given value.
For example, for the following tree:
- n1 (Value: 1, Left: null, Right: null)
- n2 (Value: 2, Left: n1, Right: n3)
- n3 (Value: 3, Left: null, Right: null)
Call to contains(n2, 3) should return True since a tree with root at n2 contains number 3.
Python 3.6.5
- Example case: Wrong answer
- Correctness: Wrong answer
- Performance test on a large tree: Wrong answer