How can I tell if this matrix is a Binary Search Tree or Binary Tree.

Question

I’m trying to answer the following questions but I’m not really sure if matrix is a Binary Search Tree or Binary Tree. Is there any way to tell?

Find the least common ancestor between two nodes on a binary search tree. The least common ancestor is the farthest node from the root that is an ancestor of both nodes. For example, the root is a common ancestor of all nodes on the tree, but if both nodes are descendents of the root's left child, then that left child might be the lowest common ancestor. You can assume that both nodes are in the tree, and the tree itself adheres to all BST properties. The function definition should look like question4(T, r, n1, n2), where T is the tree represented as a matrix, where the index of the list is equal to the integer stored in that node and a 1 represents a child node, r is a non-negative integer representing the root, and n1 and n2 are non-negative integers representing the two nodes in no particular order. For example, one test case might be

question4([[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 0, 0, 0, 0]],
3,
1,
4)

Answer 1

I think, the matrix represents the following graph:

The matrix should read as follows:

0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 1
0 0 0 0 0

Row 0 represents node 0. It has a 1 at index 1, i.e. node 1 is a child of node 0. The same method should apply to the other rows. E.g. node 0 and node 4 are children of node 3.

To check if the graph is a tree, do the following: Every node in a tree (except the root) has exactly one parent. Hence, you need to make sure that all columns in the matrix have exactly one 1 entry (except for the root column, which should have no 1 entries).

To check if the tree is a binary tree, you need to check if a node has at most two children. You can do this by checking if every row has at most two 1 entries.

To check if a binary tree is a binary search tree, you have to check if there is at most one child in every subtree. I.e. in row i, there must be at most one 1 entry among entries [0 .. i-1] and at most one 1 entry among entries [i+1 .. n-1]. As greybeard pointed out, this condition is not sufficient because it does not regard higher-level ancestors. To check this, you need to construct the tree and traverse from root to leaves, checking if nodes fall in the allowed interval.