Check if the binary tree is malformed. :raise binarytree.exceptions.NodeReferenceError: If there is a cyclic reference to a node in the binary tree. :raise binarytree.exceptions.NodeTypeError: If a node is not an instance of :class:`binarytree.Node`.
(self)
| 676 | print("\n" + "\n".join((line.rstrip() for line in lines))) |
| 677 | |
| 678 | def validate(self) -> None: |
| 679 | """Check if the binary tree is malformed. |
| 680 | |
| 681 | :raise binarytree.exceptions.NodeReferenceError: If there is a |
| 682 | cyclic reference to a node in the binary tree. |
| 683 | :raise binarytree.exceptions.NodeTypeError: If a node is not an |
| 684 | instance of :class:`binarytree.Node`. |
| 685 | :raise binarytree.exceptions.NodeValueError: If node value is invalid. |
| 686 | |
| 687 | **Example**: |
| 688 | |
| 689 | .. doctest:: |
| 690 | |
| 691 | >>> from binarytree import Node |
| 692 | >>> |
| 693 | >>> root = Node(1) |
| 694 | >>> root.left = Node(2) |
| 695 | >>> root.right = root # Cyclic reference to root |
| 696 | >>> |
| 697 | >>> root.validate() # doctest: +IGNORE_EXCEPTION_DETAIL |
| 698 | Traceback (most recent call last): |
| 699 | ... |
| 700 | binarytree.exceptions.NodeReferenceError: cyclic node reference at index 0 |
| 701 | """ |
| 702 | has_more_nodes = True |
| 703 | nodes_seen = set() |
| 704 | current_nodes: List[Optional[Node]] = [self] |
| 705 | node_index = 0 # level-order index |
| 706 | |
| 707 | while has_more_nodes: |
| 708 | |
| 709 | has_more_nodes = False |
| 710 | next_nodes: List[Optional[Node]] = [] |
| 711 | |
| 712 | for node in current_nodes: |
| 713 | if node is None: |
| 714 | next_nodes.append(None) |
| 715 | next_nodes.append(None) |
| 716 | else: |
| 717 | if node in nodes_seen: |
| 718 | raise NodeReferenceError( |
| 719 | f"cyclic reference at Node({node.val}) " |
| 720 | + f"(level-order index {node_index})" |
| 721 | ) |
| 722 | if not isinstance(node, Node): |
| 723 | raise NodeTypeError( |
| 724 | "invalid node instance at index {}".format(node_index) |
| 725 | ) |
| 726 | if not isinstance(node.val, _NODE_VAL_TYPES): |
| 727 | raise NodeValueError( |
| 728 | "invalid node value at index {}".format(node_index) |
| 729 | ) |
| 730 | if not isinstance(node.value, _NODE_VAL_TYPES): # pragma: no cover |
| 731 | raise NodeValueError( |
| 732 | "invalid node value at index {}".format(node_index) |
| 733 | ) |
| 734 | if node.left is not None or node.right is not None: |
| 735 | has_more_nodes = True |