Binary Tree Subtree Analysis

Overview

This repository contains a Python implementation for constructing a binary tree from a given input, analyzing the maximum subtree sum, and finding the path to the node with the maximum subtree sum. The implementation uses a divide-and-conquer approach to solve the problem efficiently.

Features

• Tree Construction: Build a binary tree from a list of values, with '*' representing the root, '+' for internal nodes, and numerical values for leaf nodes.
• Subtree Analysis: Calculate the maximum sum of any subtree and identify the node contributing to this maximum sum.
• Path Finding: Trace the path from the node with the maximum subtree sum to the root of the tree.

Code Explanation

• Node Class: Represents a node in the binary tree with attributes for value, parent, left child, and right child.
• create_tree Function: Constructs the binary tree from a list of values. The tree is built in reverse order to ensure correct placement of nodes.
• divide_and_conquer Function: Recursively calculates the maximum sum of subtrees and identifies the node with the maximum subtree sum.
• find_path_of_max_subtree Function: Traces the path from the node with the maximum subtree sum to the root, returning the path as a string.
• print_tree Function: Prints the structure of the tree for visual representation, showing connections between nodes.
• Main Function: Creates a sample tree, finds the maximum subtree sum and path, and prints the results.

Usage

To use this implementation, clone the repository and run the analysis.py script with the desired input values.

python analysis.py

Hardware Requirements

• Computer or Raspberry Pi
• Python 3.x installed

Software Requirements

• Python 3.x
• Required Libraries: numpy, matplotlib, networkx
• IDE or Text Editor of your choice

Contributing

Please fork this repository and contribute by submitting pull requests. For major changes, please open an issue first to discuss what you would like to change.

Profile

Check out my GitHub profile: Esmail Sarhadi

Project Link

View this project on GitHub: Binary-Tree-Subtree-Analysis

Sponsorship

If you find this project useful, please consider sponsoring:

Sponsor

License

This project is licensed under the MIT License - see the LICENSE file for details.

Download Code

Contact

If you have any questions or suggestions, feel free to contact us at sarhadiesmail@gmail.com.