How to determine if this matrix is ​​a binary search tree or a binary tree.

Question

I am trying to answer the following questions, but Im really not sure if the matrix is ​​a binary search tree or a binary tree. Is there any way to say?

Find the least common ancestor between the two nodes in the binary search tree. The least common ancestor is the farthest node from the root, which is the ancestor of both nodes. For example, the root is the common ancestor of all nodes in the tree, but if both nodes are descendants of the root left child, then this left child may 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 a tree represented as a matrix, where the index of the list is an integer stored in this node, and 1 represents a child node, r is a non-negative integer representing the root, and n1 and n2 are non-negative integers representing two nodes in a specific 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 look like this:

 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 

Line 0 represents node 0 . It has 1 with index 1 , i.e. node 1 is a child of node 0 . The same method should apply to other lines. For instance. node 0 and node 4 are children of node 3 .

To check if a graph is a tree, do the following: Each node in the tree (except the root) has exactly one parent. Therefore, you need to make sure that all columns in the matrix have exactly one record 1 (with the exception of the root column, in which there should be no records 1 ).

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

To check if a binary tree is a binary search tree, you must check to see if there is at most one child in each subtree. That is, in line i should be no more than one record 1 among the records [0 .. i-1] and no more than one record 1 among the records [i+1 .. n-1] . As Grayboard pointed out, this condition is not enough, because he does not consider ancestors of a higher level. To check this, you need to build a tree and go from root to leaves, checking to see if the nodes fall within the allowed interval.