Tag Archives: binary search tree

LeetCode

Facebook Mülakat Sorusu – Lowest Common Ancestor of a Binary Search Tree

Leave a comment

Leetcode içerisinde bulunan “Lowest Common Ancestor of a Binary Search Tree” sorusunun açıklaması ve çözümü. Bu soruda size verilen bir binary search tree içerisinde, verilen iki tane TreeNode’un en aşağıdaki ortak parent’ını bulmanız isteniyor. Bence deneme olarak bunun iterative halini de siz yazabilirsiniz.

► LeetCode 235. Lowest Common Ancestor of a Binary Search Tree: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

► Problem açıklaması:

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia:

“The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

Output: 6

Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

Output: 2

Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1

Output: 2

Constraints:

The number of nodes in the tree is in the range [2, 105].

-109 <= The number of nodes in the tree is in the range [2, 10^5].

-10^9 <= Node.val <= 10^9

All Node.val are unique.

p != q

p and q will exist in the BST.

Hackerrank

Hackerrank “30 Days of Code” Çözümleri – Day 23: BST Level-Order Traversal

Leave a comment

Hackerrank’in 30 Days of Code içerisinde bulunan “Day 23: BST Level-Order Traversal” sorusunun açıklaması ve çözümü. Bu soruda bir binary search tree içerisinde level-order traversal işleminin nasıl yapılabileceğini öğrendik.

► Hackerrank 30 Days of Code Çözümleri – Day 23: BST Level-Order Traversal: https://www.hackerrank.com/challenges/30-binary-trees/problem

► Problem açıklaması:

Objective

Today, we’re going further with Binary Search Trees. Check out the Tutorial tab for learning materials and an instructional video!

Task

A level-order traversal, also known as a breadth-first search, visits each level of a tree’s nodes from left to right, top to bottom. You are given a pointer, root, pointing to the root of a binary search tree. Complete the levelOrder function provided in your editor so that it prints the level-order traversal of the binary search tree.

Hint: You’ll find a queue helpful in completing this challenge.

Function Description

Complete the levelOrder function in the editor below.

levelOrder has the following parameter:

– Node pointer root: a reference to the root of the tree

Prints

– Print node.data items as space-separated line of integers. No return value is expected.

Input Format

The locked stub code in your editor reads the following inputs and assembles them into a BST: The first line contains an integer, T (the number of test cases).

The T subsequent lines each contain an integer, data, denoting the value of an element that must be added to the BST.

Output Format

Print the data value of each node in the tree’s level-order traversal as a single line of N space-separated integers.

Sample Input

6

3

5

4

7

2

1

Sample Output

3 2 5 1 4 7

Explanation

The input forms the following binary search tree:

https://s3.amazonaws.com/hr-challenge-images/17176/1461696188-8eddd12300-BST.png

We traverse each level of the tree from the root downward, and we process the nodes at each level from left to right. The resulting level-order traversal is 3-2-5-1-4-7, and we print these data values as a single line of space-separated integers.

Hackerrank

Hackerrank “30 Days of Code” Çözümleri – Day 22: Binary Search Trees

Leave a comment

Hackerrank’in 30 Days of Code içerisinde bulunan “Day 22: Binary Search Trees” sorusunun açıklaması ve çözümü. Bu soruda bir binary search tree‘nin yüksekliğini hesapladık.

► Hackerrank 30 Days of Code Çözümleri – Day 22: Binary Search Trees: https://www.hackerrank.com/challenges/30-binary-search-trees/problem

► Problem açıklaması:

Objective

Today, we’re working with Binary Search Trees (BSTs). Check out the Tutorial tab for learning materials and an instructional video!

Task

The height of a binary search tree is the number of edges between the tree’s root and its furthest leaf. You are given a pointer, root, pointing to the root of a binary search tree. Complete the getHeight function provided in your editor so that it returns the height of the binary search tree.

Input Format

The locked stub code in your editor reads the following inputs and assembles them into a binary search tree: The first line contains an integer, n, denoting the number of nodes in the tree.

Each of the n subsequent lines contains an integer, data, denoting the value of an element that must be added to the BST.

Output Format

The locked stub code in your editor will print the integer returned by your getHeight function denoting the height of the BST.

Sample Input

7

3

5

2

1

4

6

7

Sample Output

3

Explanation

The input forms the following BST:

https://s3.amazonaws.com/hr-challenge-images/17175/1459894869-6bb53ce6eb-BST.png

The longest root-to-leaf path is shown below:

https://s3.amazonaws.com/hr-challenge-images/17175/1459895368-4955f9ce74-LongestRTL.png

There are 4 nodes in this path that are connected by 3 edges, meaning our BST’s height = 3. Thus, we print 3 as our answer.