Partial BST Problem Statement

Check if a given binary tree is a Partial Binary Search Tree (BST). A Partial BST adheres to the following properties:

  • The left subtree of a node contains only nodes with data less than or equal to the node’s data.
  • The right subtree of a node contains only nodes with data greater than or equal to the node’s data.
  • Both left and right subtrees must also be Partial BSTs.

Input:

The first line contains an integer 't', the number of test cases. Each test case is described by the next lines:
The elements of the tree in level order form, space-separated. Use -1 to denote the absence of a child node.

Output:

For each test case, return 'true' if the binary tree is a Partial BST, 'false' otherwise. Each result will be on a separate line.

Example:

Input:
1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output:
true

Constraints:

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 1000
  • -109 ≤ data ≤ 109
Note:

You are not required to print anything; the implementation should simply return the result.

AnswerBot
4d

Check if a binary tree is a Partial Binary Search Tree (BST) based on specific properties.

  • Traverse the tree in level order and check if each node satisfies the properties of a Partial BST.

  • Use recursio...read more

Help your peers!
Add answer anonymously...
Jupiter Money Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter