Write a recursive function that takes a binary tree and decides whether it is a

Question

Write a recursive function that takes a binary tree and decides whether it is a search tree or not. I suggest that you start by writing two helper functions (again recursive). One function checks that an integer n is greater than all items in tree t. This function returns

true if tree t is empty (t == NULL). The other function checks that an integer n is smaller than all items in tree t (again return true if t == NULL). No loops allowed!

You need a way to read trees from the input. Use an input file called test.txt. Assume that all items in the tree are positive. The file will contain the items in the tree, in preorder, with the number -1 representing an empty tree. So a tree t1 with item 5 and two empty subtrees is

5 -1 -1

A tree with item 3, empty left subtree, and t1 as its right subtree is

3 -1 5 -1 -1

You may wish to use hand-built trees for testing. You can also use the following examples:

5 -1 8 -1 -1 (search tree)

5 4 -1 -1 3 -1 -1 (not a search tree, because 3 < 5)

Read one tree from the input file, and print "true" (it's a search tree) or "false" (it's not).

 

 

 

 

 

Check to see if a binary tree is a binary search tree

There is also another class that has a field for the data in the node along with fields with the left and right node.

Explanation / Answer

This is a nonrecursive way. You make it into an ArrayList and check the nodes where a node at location i has its children at 2i+1 and 2i+2 or in other words, a child at i has its parent at (i-1)/2 (its an integer which chops of any decimal). And then you can use if statements to check the parent is greater than both children. Here is the method to make an ArrayList from a tree: private ArrayList levelOrderTraversal(BinaryTreeNode t) { int index = 0; ArrayList nodes = new ArrayList(); ArrayList result = new ArrayList(); BinaryTreeNode current = t; nodes.add(current); while (index

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.